27945번 - 슬슬 가지를 먹지 않으면 죽는다

문제

키위새는 가지와 사랑에 빠지면서 가지로 맛있는 요리를 하기 위해 1ドル$번부터 $N$번까지의 번호가 붙은 $N$개의 요리 학원에 다니기 시작했다.

각 요리 학원 사이에는 총 $M$개의 양방향 길이 있고, $i$번째 길에는 정확히 $t_i$일에만 문을 여는 가지 디저트 노점이 있다. ($t_i$는 모두 다르다.) 아직 가지 요리를 배우는 중인 키위새는 직접 가지 요리를 해 먹지는 못하다 보니 가지 부족증(hypomelitzemia)이 발생했다. 키위새는 이제 매일 노점에 들러 가지 디저트를 먹지 않으면 쓰러지게 된다. 심지어 기억력도 퇴화해 $N-1$개의 길만을 기억할 수 있게 되었다!

모든 요리 학원에 다닐 수 있도록 $N-1$개의 길을 골랐을 때, 키위새가 쓰러지는 날이 $d$일차라고 하자. 날짜가 1ドル$일차부터 시작할 때, $d$의 최댓값을 구해보자.

입력

첫째 줄에 요리 학원의 수 $N,ドル 길의 수 $M$이 주어진다. $(2\le N\le 10^5;$ $N-1\le M\le\min\left(5\times 10^5, {N\choose 2}\right))$

둘째 줄부터 $M$개 줄에 각 길이 연결하는 두 학원의 번호 $u_i,ドル $v_i,ドル 길에 있는 노점이 여는 날 $t_i$가 주어진다. $(1\le u_i,v_i\le N;$ $u_i\ne v_i;$ 1ドル\le t_i\le 10^9;$ $t_i\ne t_j)$

각 요리 학원에서 길을 따라 모든 요리 학원으로 가는 방법이 존재하는 경우만 주어진다.

두 요리 학원 사이를 곧바로 잇는 길은 많아야 하나이다.

출력

첫째 줄에 $d$의 최댓값을 출력한다.

제한

힌트