问题:

求城市间最短通路. 设有如图所示的N座城市, 相邻城市之间有若干条通路, 线上的数字表示通路的距离. 试求出从1到n的最短距离.

输入格式：

n e (1<=n<=200代表顶点数，1<=e<=600代表边数，下面有e行，代表e 条有向边,注意：会有重边,数据保证没有环)

输出格式：

输出最短距离

输入样例：

7 9
1 2 5
1 3 2
2 4 3
2 5 2
3 5 7
3 6 4
4 7 4
5 7 3
6 7 5

输出样例：

10