题目描述

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

输入格式

第一行给出n个城市（城市编号1~n），和m条公路，1<=n,m<=100。
接下来每一行类似“a b c”这样的数据，表示有一条路可以从城市a到城市b，并且路程为c公里。

输出格式

一行，输出1到n的最短路径，如果无法到达输出-1。

样例数据

input

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

output

7