1769. Way to Escape

Kid has got the diamond ring after he got the password. After that he tried to escape as quickly as possible. Now give you the map, point 0 stands for Kid, point 1 stands for the exit.

输入格式

There are n (2<=n<=100) points (from 0 to n-1), r roads, given in a line. Different distances between points are given, one line for each road with three integers s, e, l(0<=s, e<=n-1, 0<l<=1000), stands for the road between the point s and e, length l.

输出格式

Please find out the shortest way for Kid to escape. Just output the length of the way you’ve found.

样例

Input
5 6
0 2 2
0 3 2
2 3 3
0 4 12
3 1 34
4 1 24

Output
36


91 人解决，110 人已尝试。

154 份提交通过，共有 319 份提交。

2.9 EMB 奖励。