You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

WXY童鞋今天要出去旅游啦（他现在在北京为1号城市），决定去朝鲜平壤（N号城市）。但是很穷的WXY没有钱坐飞机，只好坐汽车去朝鲜了。但是车上的百度地图十分不给力，每回不是把WXY带到了山顶上就是带到了下水道里（WXY的车能开进下水道，真是666666）。WXY被百度导航整得苦不堪言。还好WXY大神事先准备了一张有N个节点，M条公路的只有火星人才能看懂的图。作为大神的WXY才懒得去计算这么简单的问题呢，所以他强制你帮他计算从北京到平壤的最短路径是什么。

Input Format

*第一行：两个数N与M代表有N个城市，M条公路。

*接下来的M行：每行有三个数a,b,c代表城市a,b之间有一条长度为c的公路。

并且路径是单向的，表示a->b的长度为c

Output 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

9