Description

暑假小哼想到去小哈家里去玩，小哼和小哈住在不同的城市，并且小哼之前从来没有去过小哈家，这是小哼第一次上门。怎么办呢？小哼便想起了百度地图。百度地图一下子就给出了从小哼家到小哈家的最短行车方案。爱思考的小哼想知道百度地图是如何计算出最短行车距离的。下面是城市的地图：

Input Format

输入是这样的：

5 8

1 2 2

1 5 10

2 3 3

2 5 7

3 1 4

3 4 4

4 5 5

5 3 3

第一行的5表示5个城市，8表示8条公路。

接下来8行每行3个数a,b,c，表示城市a到城市b有一条长为c的路。（注意是单程的）。

Output Format

输出小哼（1号点）到小哈（5号点）的最短路程

5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3​

9​

Source

搜索 DFS 最短路径