城市之间的最短路

题目描述

小丁同学准备去A国旅游，他买了一张A国的地图，地图标出了A国著名的 $n$ 个旅游热门城市，并标注了这 $n$ 个城市之间有 $m$ 条双向路线相连以及每条双向路线的长度。 请你编程帮助小丁求出其中两个城市之间的最短距离。

输入格式

输入第一行为两个正整数 $n$ （ $n \le 10$ ）和 $m$ （ $m \le n \times (n-1)/2$ ）， $n$ 表示城市个数， $m$ 表示线段个数。 接下来 $m$ 行，每行输入三个整数 $a,b$ 和 $l$ ，表示 $a$ 市与 $b$ 市之间存在一条线段，线段长度为 $l$ 。（ $a$ 与 $b$ 不同，且本题的数据中两个城市之间最多只有一条路） 每组最后一行输入两个整数 $x$ 和 $y$ ，表示问题： $x$ 市与 $y$ 市之间的最短距离是多少。（ $x$ 与 $y$ 不同） 城市标号为 $1 \sim n$ ， $1 \le l \le 20$ 。

输出格式

输出 $x$ 市与 $y$ 市之间的最短距离，如果 $x$ 市与 $y$ 市之间非连通，则输出 No path 。

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

3

提示

无