说明

小丁同学准备去$A$国旅游，他买了一张$A$国的地图，地图标出了$A$国著名的$n$个旅游热门城市，并标注了这$n$个城市之间有$m$条路线相连以及每条路线的长度。

请你编程帮助小丁求出其中两个城市之间的最短距离。

输入格式

输入第一行为两个正整数$n$和$m$，$n$表示城市个数，$m$表示线段个数。

接下来$m$行，每行输入三个整数$a，b$和$l$，表示$a$市与$b$市之间存在一条线段，线段长度为$l$。（$a$与$b$不同，且本题的数据中两个城市之间最多只有一条路）

每组最后一行输入两个整数$x$和$y$，表示问题：$x$市与$y$市之间的最短距离是多少。（$x$与$y$不同） 城市标号为1~$n$

输出格式

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

样例

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

3

数据范围

• $n\leqslant 10$
• $m\leqslant n*(n-1)/2$
• $l\leqslant 20$