当深入南蛮之地时，遇当地人绘得地图，发现各地分别由各个寨主据守，若诸葛亮想兵分多路进军，尽快占领各个山寨(必须占领所有山寨)，并且最终所有士兵都汇聚到孟获所在山寨，若给你一次穿越的机会，你用程序告诉诸葛亮最少需要多少天才能完成这个任务。假设军队足够多，各分队行军速度一样，且诸葛亮神机妙算，到达每个山寨即日可以攻克。
| Time Limit | $1$ 秒/Second(s) | Memory Limit | $512$ 兆字节/Megabyte(s) |
| 提交总数 | $48$ | 正确数量 | $42$ | "
| 裁判形式 | 标准裁判/Standard Judge | 我的状态 | 尚未尝试 |
| 难度 | 分类标签 | 图论 |
当深入南蛮之地时，遇当地人绘得地图，发现各地分别由各个寨主据守，若诸葛亮想兵分多路进军，尽快占领各个山寨(必须占领所有山寨)，并且最终所有士兵都汇聚到孟获所在山寨，若给你一次穿越的机会，你用程序告诉诸葛亮最少需要多少天才能完成这个任务。假设军队足够多，各分队行军速度一样，且诸葛亮神机妙算，到达每个山寨即日可以攻克。
接下来m行，每行三个整数i,j,k(0=<i,j<n,k<=10^4)，分别表示山寨i和山寨j之间有一条路，在这条路上需要行军k天，接下来一行两个整数s,t(0<=s,t<=n-1)，分别表示诸葛亮所在部队的起点和孟获山寨所在终点的编号
2
5 6
0 1 2
1 2 2
3 1 2
4 0 3
3 2 3
3 4 1
4 3
5 5
1 0 1
1 2 3
1 3 3
4 2 2
3 4 1
4 2
7
9