阿Q准备去参加骑车比赛，比赛在 n 个城市间进行，编号从 1 到 n。选手们都从城市 1 出发，终点在城市 n。

已知城市间有 m 条道路，每条道路连接两个城市，注意道路是双向的。现在阿Q知道了他经过每条道路需要花费的时间，他想请你帮他计算一下，他这次比赛最少需要花多少时间完成。

输入格式

第一行输入两个整数 $n, m（1 \leq n \leq 1,000, 1 \leq m \leq 5,000）$，分别代表城市个数和道路总数。接下来输入 m 行，每行输入三个数字 $a, b, c（1 \leq a, b \leq n, 1 \leq c \leq 200 ）$，分别代表道路的起点和道路的终点，以及阿Q骑车通过这条道路需要花费的时间。保证输入的图是连通的。

输出格式

输出一行，输出一个整数，输出阿Q完成比赛需要的最少时间。

输出时每行末尾的多余空格，不影响答案正确性

要求使用「文件输入输出」的方式解题，输入文件为 match.in，输出文件为 match.out

样例输入

5 6
1 2 2
2 3 3
2 5 5
3 4 2
3 5 1
4 5 1

样例输出

6