도로 봉쇄

매일 아침 농부 존(FJ)은 집에서 헛간까지 농장을 가로질러 걸어간다. 농장은 $N$개의 밭($1 \le N \le 100$)으로 이루어져 있으며, 각각 양의 길이를 가진 $M$개의 양방향 길($1 \le M \le 10{,}000$)로 연결되어 있다. FJ의 집은 $1$번 밭에, 헛간은 $N$번 밭에 있다. 두 밭을 잇는 길은 많아야 하나뿐이며, 어떤 밭에서든 다른 모든 밭으로 이동할 수 있다. FJ는 이동할 때 항상 전체 길이가 최소가 되는 경로를 택한다.

장난기 많은 젖소들은 FJ의 아침 산책을 방해하려 한다. 젖소들은 $M$개의 길 중 정확히 하나에 건초 더미를 쌓아 그 길의 길이를 두 배로 만든다. 젖소들은 집에서 헛간까지 FJ의 최단 경로 길이가 최대한 많이 늘어나도록 길을 고르려 한다. 젖소들이 만들 수 있는 최대 증가량을 구하라.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• $2 \dots M+1$번째 줄: $j+1$번째 줄은 $j$번째 양방향 길을 세 정수 $A_j$, $B_j$, $L_j$로 나타낸다. 밭 $A_j$와 $B_j$(각각 $1 \dots N$ 범위)는 길이 $L_j$($1 \le L_j \le 1{,}000{,}000$)인 길로 연결된다.

• 첫째 줄: 길 하나의 길이를 두 배로 만들어 얻을 수 있는, $1$번 밭에서 $N$번 밭까지 FJ 최단 경로 길이의 최대 증가량.

예시에서는 밭이 $5$개, 길이 $7$개 있다. 처음에 집($1$번 밭)에서 헛간($5$번 밭)까지의 최단 경로는 $1 \to 3 \to 4 \to 5$이며 전체 길이는 $1 + 3 + 2 = 6$이다.

젖소들이 밭 $3$과 밭 $4$ 사이 길의 길이를 두 배로($3$에서 $6$으로) 만들면, FJ의 최단 경로는 $1 \to 3 \to 5$가 되어 전체 길이가 $1 + 7 = 8$이 되고, 이는 이전보다 $2$만큼 길다. 다른 어떤 길 하나로도 이보다 더 크게 늘릴 수 없으므로 답은 $2$이다.