探索宝藏

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

毛线是一个富有探索精神的年轻人,他最近发现一个神秘的地方,这里有很多价值连城的宝藏,因此毛线打算对它进行一番探索。毛线手中有关于这个地方各个宝藏的一些信息,比如它们之间的距离。当毛线得到了一个宝藏后,他想知道离另一个宝藏有多远,你能告诉他吗?
 

Input

 输入包含多组数据,对于每组测试数据:
第一行输入 n(2<=n<=100),m(1<=m<=1000),n 表示宝藏的数量,m 表示各个宝藏之间的路径数。
接下来 m 行,每行输入 3 个数,x,y(1<=x,y<=100),w(1<=w<=1000)。x,y 分别表示宝藏 x 与宝藏 y;w 表示宝藏 x 与宝藏 y 之间的距离。
然后输入 s(1<=s<=n),d(1<=d<=n),表示宝藏 s 与宝藏 d。
 

Output

 对于每一组数据,找出宝藏 s 到宝藏 d 的最短的距离。如果两个宝藏可以相互到达,输出它们之间的最短距离;否则,输出-1。
 

Sample Input

3 2
1 2 2
2 3 4
1 3
4 3
2 1 5
2 3 3
1 3 2
1 4

Sample Output

6
-1

Hint

 

Source