2044: 【入门】城市之间的最短路
内存限制：32 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：29
解决：17
题目描述
小丁同学准备去A国旅游，他买了一张A国的地图，地图标出了A国著名的n个旅游热门城市，并标注了这n个城市之间有m条路线相连以及每条路线的长度。
请你编程帮助小丁求出其中两个城市之间的最短距离。
请你编程帮助小丁求出其中两个城市之间的最短距离。
输入
输入第一行为两个正整数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。
接下来m行，每行输入三个整数a，b和l，表示a市与b市之间存在一条线段，线段长度为l。（a与b不同，且本题的数据中两个城市之间最多只有一条路）
每组最后一行输入两个整数x和y，表示问题：x市与y市之间的最短距离是多少。（x与y不同）
城市标号为1~n，l<=20。
输出
输出x市与y市之间的最短距离，如果x市与y市之间非连通，则输出“No path”。
样例输入 复制
4 4
1 2 4
1 3 1
1 4 1
2 3 1
2 4样例输出 复制
3