#P2057. G.亲戚来了

G.亲戚来了

Bob 一家人要去下馆子,为什么呢?因为他姑姑的大爷的叔叔的孙子的表叔的婶婶的儿子来了,亲戚来了当然要下馆子,可是Bob家在偏僻的小山屯,饭店在城里啊<o:p></o:p>

距离老远了。。。。。<o:p></o:p>

于是他们决定坐车去,可是家里面就有一辆车啊,还是个拖拉机。。。。。。<o:p></o:p>

并且,山路不好走啊,不能过超过这条路的载客量,于是不得不再回去一趟。。。。。。<o:p></o:p>

比如,在下面的地图,假设Bob家在1号村庄,饭店在7号村庄,其中一条边表示给条路上的最大载客量<o:p></o:p>


现在Bob要将他的亲戚以及家人99人(不包含Bob)送到城里面,选择的最好路线是1->2->4->7<o:p></o:p>

并且往返5次。。。。。现在我们请你帮忙计算Bob将亲戚以及家人送到城镇里面所用的最少往返次数。。。<o:p></o:p>

Input

输入包含若干组数据,每组数据的第一行有两个整数n(n<=100)和r,分别表示村庄的数量,和道路的数量,接下来的R行每行有三个整数
u,v,w;表示u号村庄到v号村庄有一条路以及这条路的最大载客量为w,
随后的一行三个数x,y,d,表示Bob的家在x号村庄,饭店在y号村庄以及Bob和他亲戚的总人数

Output

输出最少的往返的次数,如果到达不了请输出-1;

Sample Input

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99

Sample Output

5

HINT

Source