魔法学院由 N 座建筑（编号为 1 \sim N）和 M 条双向道路构成，建筑之间直接或者间接连通。任意两个建筑之间最多只有 1 条道路。
魔法学院的老师和同学们都精于计算，他们如果想要从编号为 X 建筑去编号为 Y 的建筑，总是会找一条最短的路径走过去。
A 老师住在 1 号建筑，每天他都会去 N 号建筑给同学们上魔法课。就在昨天，他刚刚给同学们讲解过一个魔法，施展该魔法，可以任意的把魔法学院的一条道路长度翻倍。
今天，A 老师要来 N 号建筑查看同学们魔法学习的情况。班级的 B 同学决定今天用一下这个魔法，把学院的某条道路（只能选择一条）长度翻倍，他希望 A 老师因为他施展了魔法，更晚到 N 号建筑给他们上课，这样他们就可以在老师来之前有更多的时间练习。
请编程计算出，因为 B 同学施展魔法，最多会使得 A 老师多走多长的路？
第 1 行读入 N,M。
接下来的 M 行，每行有三个整数 X_i,Y_i,L_i，代表编号为 X_i 和 Y_i 的建筑之间有一条长度为 L_i 的双向道路。
输出 B 同学施展魔法之后，A 老师多走的最长的路径长度。
5 8 2 3 7 2 4 12 4 5 8 3 1 3 5 2 12 4 3 4 4 1 16 3 5 7
5
8 12 2 5 18 2 1 6 2 6 7 6 7 18 2 3 12 6 4 10 3 8 14 7 1 14 7 2 1 2 4 7 5 4 18 8 7 16
9
12 20 9 2 15 9 5 19 2 6 7 6 12 7 6 4 17 6 7 10 9 11 4 4 3 4 11 8 9 11 10 3 2 1 14 4 8 15 12 2 4 3 2 12 3 1 8 10 4 1 4 9 5 8 2 3 8 5 6 2 5 17
6
对于 40\% 的数据，N \le 50，M \le 500。
对于 100\% 的数据，1 \le N \le 100，1 \le M \le 5000，1 \le X_i,Y_i \le N，1 \le L_i \le 10^6。