길 막기

FJ는 매일 아침 일어나 집에서 헛간까지 농장을 가로질러 걸어간다. 농장은 밭 $N$개($1 \le N \le 250$)로 이루어져 있고, 밭 사이는 길이가 정해진 양방향 길 $M$개($1 \le M \le 25{,}000$)로 이어져 있다. FJ의 집은 1번 밭에 있고, 헛간은 $N$번 밭에 있다. 같은 두 밭을 잇는 길이 두 개 이상 놓인 경우는 없고, 어느 두 밭 사이든 길을 따라 오갈 수 있다. FJ는 한 밭에서 다른 밭으로 갈 때 언제나 길이의 합이 가장 작은 경로를 고른다.

소들은 늘 그렇듯 장난을 칠 생각으로 FJ의 아침 일과를 방해하기로 했다. 농장의 길 $M$개 중 정확히 하나를 골라 그 위에 건초 더미를 쌓아서 그 길의 길이를 두 배로 만들 계획이다. 소들은 집에서 헛간까지 FJ가 걷는 최단 거리가 가장 많이 늘어나도록 막을 길을 고른다. 소들이 FJ의 경로를 얼마나 늘릴 수 있는지 구하라.

• 첫째 줄에 정수 $N$과 $M$이 공백을 사이에 두고 주어진다.
• 둘째 줄부터 $1+M$번째 줄까지, $j+1$번째 줄에는 $j$번 양방향 길을 나타내는 세 정수 $A_j$, $B_j$, $L_j$가 공백을 사이에 두고 주어진다. $A_j$와 $B_j$는 그 길이 잇는 두 밭의 번호로 $1$ 이상 $N$ 이하이고, $L_j$는 그 길의 길이로 $1$ 이상 $1{,}000{,}000$ 이하이다.

• 길 하나의 길이를 두 배로 늘려서 만들 수 있는 FJ의 최단 경로 길이의 최대 증가량을 첫째 줄에 출력한다.