天气逐渐变冷,年老体弱的越越鸟打算去南方某座温度适宜的城市过冬,但由于翅膀严重老化,最远飞行距离有限,请你为可怜的越越鸟计算飞行所需的最短距离,以让它能做好心理准备。
输入包含多组测试数据。
每组输入第一行为两个正整数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。
对于每组输入,输出x市与y市之间的最短距离,如果x市与y市之间非连通,则输出“No path”。