Description

一天小明捧着一本世界地图在看，突然小明拿起笔，将他最爱的那些城市标记出来，并且随机的将这些城市中的某些用线段两两连接起来。

小明量出了每条线段的长度，现在小明想知道在这些线段组成的图中任意两个城市之间的最短距离是多少。

Format

Input

输入包含多组测试数据。

每组输入第一行为两个正整数$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$。

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

Limitation

1s, 1024KiB for each test case.