该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

city.in city.out

Background

暑假了,小W的时间又开始多起来了,于是他决定去旅游,这并不奇怪，因为旅游的确很好玩。 小W同学准备去长沙旅游，他买了一张长沙的地图，地图标出了长沙著名的n个旅游热门景点，并标注了这n个景点之间有m条路线相连以及每条路线的长度。

请你编程帮助小W求出其中两个景点之间的最短距离。

Input

输入第一行为两个正整数n（n<=20）和m（m<=n*(n-1)/2），n表示城市个数，m表示路线条数。

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

每组最后一行输入两个整数x和y，表示问题：x景点与y景点之间的最短距离是多少。（x与y不同）

Output

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

Samples

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

3

城市标号为1~n，l<=20 .