등교길

매일 아침, 지훈이는 집에서 학교로 가기 위해 중간에 상가 지역을 가로질러 갑니다. 상가는 N개의 필드로 구성되어 있으며 (1 <= N <= 100), 이들은 각각 길이를 가진 M개의 양방향 경로로 연결되어 있습니다(1 <= M <= 10,000). 

지훈의 집은 1번 필드에 위치해 있고, 학교는 N번 필드에 있습니다. 어떤 필드 쌍도 여러 개의 중복 경로로 연결되어 있지 않으며, 적절한 경로의 순서를 따라 걸으면 상가 안의 모든 필드를 이동하는 것이 가능합니다. 한 필드에서 다른 필드로 이동할 때, 지훈은 항상 총 길이가 최소가 되는 경로의 순서를 선택합니다.

동네의 깡패들이 지훈의 등교길을 방해하기로 결정했습니다. 그들은 상가 안의 M개의 경로 중 하나에 장애물을 쌓아 등교길 경로를 두 배로 만들 계획입니다. 깡패들은 지훈의 집에서 학교까지의 거리가 최대한 늘어나게끔 경로를 막고자 합니다.

깡패들이 지훈의 경로를 얼마나 늘릴 수 있는지 알려주세요.

• 첫 번째 줄: 두 개의 공백으로 분리된 정수, N (1 <= N <= 100)과 M (1 <= M <= 10,000).
• 두 번째 줄..1+M 번째 줄 : j+1 번째 줄은 세 개의 공백으로 분리된 정수로 j 번째 양방향 경로를 설명합니다: A_j B_j L_j, 여기서 A_j와 B_j는 경로가 연결하는 필드를 나타내는 가 인덱스이며, 범위는 1..N이며, L_j는 경로의 길이 (범위 1...1,000,000).

• 첫 번째 줄: 단일 경로의 길이를 두 배로 만듦으로써 지훈의 가장 짧은 경로의 총 길이 증가 최대치.