건초가 떨어졌다

소들이 건초를 다 써버렸다. 이는 당장 해결해야 하는 끔찍한 상황이다. 베시는 다른 농장들을 방문해 각 농장의 건초 사정을 조사하려 한다. 농장은 $N$개($2 \le N \le 2,000$)이며 1번부터 $N$번까지 번호가 매겨져 있다. 베시는 1번 농장에서 출발한다. 농장들을 잇는 $M$개($1 \le M \le 10,000$)의 양방향 도로 가운데 일부 또는 전부를 지나게 된다. 도로의 길이는 $1,000,000,000$을 넘지 않는다. 같은 두 농장 사이에 길이가 다른 도로가 여럿 있을 수 있다. 모든 농장은 어떤 경로로든 1번 농장과 연결되어 있다.

베시는 도로 길이 1단위마다 물 1온스가 필요하다. 농장마다 물을 얻을 수 있으므로 베시가 신경 쓰는 것은 가장 긴 도로의 길이뿐이다. 베시는 들고 다녀야 하는 물의 양이 최소가 되도록 농장 사이의 경로를 고른다. 가장 긴 도로의 길이를 줄이기 위해 이미 지난 도로를 되돌아갈 수도 있다.

첫 줄에 공백으로 구분된 정수 $N$과 $M$이 주어진다. 이어지는 $M$개의 줄에는 공백으로 구분된 정수 $A_i$, $B_i$, $L_i$가 각각 주어지며, 이는 $A_i$번 농장과 $B_i$번 농장을 잇는 길이 $L_i$의 도로를 뜻한다.

경로가 최적일 때 베시가 지나야 하는 가장 긴 도로의 길이를 정수 하나로 출력한다.

2번 농장에 가려면 길이 23인 도로를 지난다. 3번 농장에 가려면 길이 43인 도로를 지난다. 용량을 43으로 하면 도로에 들어서기 전에 물탱크를 가득 채워 두는 조건에서 이 도로들을 모두 지날 수 있다.