HZNUOJ

过冬

Tags:     弗洛伊德  Dijk
Time Limit:  1 s      Memory Limit:   32 MB
Submission:596     AC:231     Score:89.98

Description

天气逐渐变冷,年老体弱的越越鸟打算去南方某座温度适宜的城市过冬,但由于翅膀严重老化,最远飞行距离有限,请你为可怜的越越鸟计算飞行所需的最短距离,以让它能做好心理准备。

Input

输入包含多组测试数据。

每组输入第一行为两个正整数n(n<=20)和m(m<=n*(n-1)/2),n表示城市个数,m表示线段个数。(线段为两个城市间的连接线)

接下来m行,每行输入三个整数a,b,和l(l<=10^9),表示a市与b市之间存在一条线段,线段长度为l。(a与b不同)

每组最后一行输入两个整数x和y,表示问题:x为越越鸟现在所在的城市,y为越越鸟打算飞往过冬的城市。城市标号为1~n。

Output

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

Samples

input
4 4 1 2 4 1 3 1 1 4 1 2 3 1 2 4
output
3

Author

CHEN, Jiachi

Source

2014杭师计算机协会第一届程序设计竞赛