비용 증가

베를란트에는 $1$번부터 $n$번까지 번호가 붙은 $n$개의 도시가 있다. $1$번 도시는 베를란트의 수도다. 일부 도시 쌍 사이에는 $m$개의 양방향 도로가 있다. 도로는 도시에서만 교차할 수 있다. 같은 두 도시 사이에 도로가 두 개 이상 있는 경우는 없고, 도시를 자기 자신과 연결하는 도로도 없다. $j$번 도로를 어느 방향으로든 이동하면 $c\_j$만큼의 세금을 내야 한다. 주어진 $m$개의 도로만 이용해 수도에서 모든 도시에 도달할 수 있다.

당신은 배달 회사의 CEO이고, 본사는 수도에 있다. 회사는 베를란트의 모든 도시에 물건을 배달하므로, 각 도시마다 수도에서 그 도시로 가는 경로 중 경로에 있는 모든 도로의 세금 합을 최소로 하는 경로를 하나씩 정했다. 수도에서 도시 $k$로 가는 이 경로의 총비용을 $d\_k$라고 하자.

정부는 정확히 하나의 도로를 정해 (어느 도로인지는 알 수 없다) 그 도로를 이용하는 세금을 올리기로 했다. 그래서 각 도로마다, 그 도로의 세금이 올라갔을 때 영향을 받는 도시가 몇 개인지 알고 싶다. 세금이 올라간 뒤 총비용이 $d\_k$인 경로를 고를 수 없으면 도시 $k$가 영향을 받는다.

첫째 줄에 도시 수와 베를란트의 도로 수를 나타내는 두 정수 $n$과 $m$이 주어진다 ($2 \le n \le 2 \cdot 10^{5}$, $n - 1 \le m \le 2 \cdot 10^{5}$).

다음 $m$개 줄에는 공백으로 구분된 세 정수 $u\_j$, $v\_j$, $c\_j$가 주어진다 ($1 \le u\_j, v\_j \le n$, $1 \le c\_j \le 10^{9}$). 이는 도시 $u\_j$와 $v\_j$ 사이의 $j$번 도로의 초기 세금이 $c\_j$라는 뜻이다.

같은 두 도시 사이에 도로가 두 개 이상 있는 경우는 없고, 도시를 자기 자신과 연결하는 도로도 없다. 주어진 도로만으로 수도에서 모든 도시에 도달할 수 있다.

$m$개의 정수를 한 줄에 하나씩 출력한다. $j$번째 정수는 $j$번 도로의 비용을 올렸을 때 영향을 받는 도시의 수여야 한다.