东非大裂谷中有一片神秘的丛林，是全世界探险家的乐园，著名黄皮肤探险家BB一直想去试试。正好我国科学家将首次对东非大裂谷进行科考，BB决定随科考队去神秘丛林探险。在出发之前，他搜集了国内外有关神秘丛林探险的资料，并绘制成一张地图：该地图上有若干安全点（包括入口点和出口点），并将这些安全点编号为$1,2,…,n$；如果一个安全点和另一个安全点有一条路直接相通，则用一条边标示；该图是一个连通图（任意两点间有至少一条路径），地图上每条路的长度和走这条路需要耗费的体力都做了标示。 KK行走速度为$1$，并知道自己体力为$K$。他想知道根据自己的体力情况能否成功地穿过丛林。

第一行两个整数$n（ \le 5000）,m（ \le 40000）$，分别表示地图上安全点的个数和边的数目；
第$2$行至第$m+1$行，每行$4$个整数$x,y,c,d$，$x,y$表示有直接相联边的两个点的编号，$c$走这条路需要耗费的体力；$d$表示边的长度；（其中$150 \le c,d \le 300$）
第$m+2$行两个整数$s,t$，分别表示安全的入口点和出口点的编号；
第$m+3$行一个整数$k$，表示BB的体力值；（$K\lt 10^9$）
同一行上的多个数据用空格隔开。

一个整数，如果BB能安全地从如入口穿过丛林到达出口，输出最短时间，否则输出$-1$。

4 5
1 2 2 3
1 3 3 5
1 4 7 10
2 4 4 6
3 4 2 6
1 4
5 · \n
 · · · \n
 · · · \n
 · · ·  \n
 · · · \n
 · · · \n
 · \n
 \n

11  \n