Problem
您将获得该国公路网的描述。你的任务 -求城市 A 和 B 之间的最短路径的长度。
输入
道路网络在输入文件中给出如下：第一行包含数字 N 和 K（1<=N<=100000，0<=K<=300000），其中 K –道路数量。下面的 K 行中的每一行都包含一条双向道路的描述——三个整数 ai、bi 和 li (1aibiN, 1li106)。这意味着从城市 ai 到城市 bi 有一条长度为 li 的路。最后一行包含两个数字 A 和 B –需要计算最短距离的城市数(1<=A,B<=N)
印记
您必须输出单个数字 –所需城市之间的距离。如果不可能通过公路从城市 A 到城市 B，打印 –1。
例子
<头>
<日>#
| 输入 |
输出 |
<正文>
| 1 |
6 4
1 2 7
2 4 8
4 5 1
4 3 100
3 1
| 115 |