罗三鸡每天清晨都从编号 $1$ 的地点前往编号 $n$ 的学校，并始终选择总长度最短的路线。城市道路构成一个无向连通图，但近期有一条道路需要施工；施工期间，这条道路的通行长度会变为原来的两倍，其他道路保持不变。

管理人员希望提前评估最不利的施工安排：可以选择任意一条道路使其长度加倍，然后重新计算从 $1$ 到 $n$ 的最短路。请输出新的最短路相对于原最短路最多会增加多少。

输入格式

第一行输入 $n,m$，随后输入 $m$ 条无向边。

输出格式

输出最大增加量。

输入 #1

4 4
1 2 1
2 4 2
1 3 2
3 4 3

输出 #1

2

输入 #2

2 1
1 2 7

输出 #2

7

输入 #3

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

输出 #3

2

数据范围与约定

• 2 ≤ $n$ ≤ 250
• $n$-1 ≤ $m$ ≤ 25000
• 1 ≤ $w$ ≤ $10^6$