핵심 도로의 최대 계수

옥타곤은 로켓 사일로, 레이더, 식당, 재향군인 사무소, 제복 창고 등 전략적으로 중요한 여러 시설을 관리한다. 이 시설들 사이의 연결망을 확보하는 것은 매우 중요하지만, 한편으로 이 연결망에 대한 위협은 최소화해야 한다. 서로 다른 두 시설을 잇는 양방향 도로마다 공격 위협 계수(줄여서 계수)가 정해져 있다. 최근 옥타곤에 입사한 조니는 한밤중에도 계수의 합을 최소로 하면서 어떤 두 시설 사이든 이동할 수 있게 하는 도로 부분집합을 계산할 수 있다. 이러한 부분집합 중 적어도 하나에 속하는 도로를 핵심 도로라고 부른다.

그러나 계수는 언제든 바뀔 수 있다. 연례 평가의 일환으로 옥타곤은 각 도로마다, 그 도로의 계수를 $x$로 두고 나머지 계수는 그대로 둘 때 그 도로가 핵심 도로가 되는 $x$의 최댓값을 구하기로 했다. 이 일은 조니에게 맡겨졌고, 그는 이 중요한 문제에서 실수할 수 없다.

첫째 줄에 두 정수 $n$과 $m$ ($1 \leq n \leq 100\,000$, $n - 1 \leq m \leq 10^6$)이 공백 하나를 사이에 두고 주어진다. 각각 옥타곤이 관리하는 시설의 수와 시설 사이의 양방향 도로의 수이다. 시설에는 $1$부터 $n$까지 연속한 자연수가 붙어 있다.

다음 $m$개 줄에는 각각 세 정수 $a$, $b$, $c$ ($1 \leq a, b \leq n$, $a \neq b$, $0 \leq c \leq 10^9$)가 공백 하나를 사이에 두고 주어진다. 시설 $a$와 $b$를 잇는 양방향 도로와 그 계수 $c$를 나타낸다. 순서 없는 쌍 $\{a, b\}$는 많아야 한 번 등장한다.

주어진 도로만으로도 어떤 두 시설 사이든 항상 이동할 수 있다.

입력에 주어진 순서대로 각 도로마다 한 줄씩, 모두 $m$개 줄을 출력한다. 특정 도로에 해당하는 줄에는 그 도로의 계수를 이 값으로 바꾸고 나머지 계수는 그대로 두었을 때 그 도로가 핵심 도로가 되는 최댓값을 자연수 하나로 출력한다. 이 값이 $10^9$보다 크거나 얼마든지 커질 수 있으면 $10^9$을 출력한다.

예제의 도로망은 다음과 같다.