2357: 【入门】城市之间的最短路(2044)

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

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

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

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

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

城市标号为 ，  。

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

3