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

Description

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

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

Input Format

输入第一行为两个正整数 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 Format

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

3

Source