Problem 1120 --最爱的城市

1120: 最爱的城市

Time Limit: 1 Sec  Memory Limit: 32 MB
Submit: 214  Solved: 90
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

一天小明捧着一本世界地图在看,突然小明拿起笔,将他最爱的那些城市标记出来,并且随机的将这些城市中的某些用线段两两连接起来。
小明量出了每条线段的长度,现在小明想知道在这些线段组成的图中任意两个城市之间的最短距离是多少。

Input

输入包含多组测试数据。
每组输入第一行为两个正整数n(n<=10)和m(m<=n*(n-1)/2),n表示城市个数,m表示线段个数。
接下来m行,每行输入三个整数a,b和l,表示a市与b市之间存在一条线段,线段长度为l。(a与b不同)
每组最后一行输入两个整数x和y,表示问题:x市与y市之间的最短距离是多少。(x与y不同)
城市标号为1~n,l<=20。

Output

对于每组输入,输出x市与y市之间的最短距离,如果x市与y市之间非连通,则输出“No path”。

Sample Input

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

Sample Output

3

HINT

Source

[Submit][Status]