동등한 파이프라인

KAIST의 $n$개 건물을 잇는 상수도관 네트워크를 건설하려고 한다. 예산 문제로 관은 $n-1$개만 사용할 수 있다. 각 관은 무향이며 서로 다른 두 건물을 잇고, $n$개 건물 모두가 관을 따라 서로 연결되어 있어야 한다. 이 관들이 네트워크를 이룬다.

신중한 계획자로서 당신은 $d$개의 서로 다른 네트워크를 설계했고, 이들을 비교하려 한다. 네트워크의 각 관은 하나의 양의 정수인 내구도로 나타낼 수 있다. 네트워크 $T$가 주어졌을 때, 서로 다른 두 건물 $i$와 $j$의 취약도 $v_{T}(i, j)$를 $i$와 $j$를 분리하게 만드는 관의 최소 내구도로 정의한다. 다시 말해 $v_{T}(i, j)$는 $i$에서 $j$로 가는 경로 위의 모든 관 가운데 최소 내구도이다.

두 네트워크 $T_{1}$과 $T_{2}$가 모든 $1 \le i < j \le n$에 대해 $v_{T_1}(i, j) = v_{T_2}(i, j)$를 만족하면 $T_{1}$과 $T_{2}$가 동등하다고 한다. 불필요한 계획을 걸러내기 위해, $d$개의 설계를 동등성을 기준으로 묶으려 한다.

첫째 줄에 두 정수 $d$와 $n$이 공백으로 구분되어 주어진다. ($d \ge 1$, $n \ge 2$, $d\cdot n \le 500\,000$)

둘째 줄부터 $d$개 설계의 설명이 주어진다. 각 설계는 $n-1$개 줄로 주어지며, 각 줄은 세 정수 $a$, $b$, $c$로 이루어진다. ($1 \le a, b \le n$, $a \neq b$, $1 \le c \le 10^{9}$) 이는 건물 $a$와 $b$를 직접 잇는 관이 있고 그 내구도가 $c$임을 뜻한다.

$d$개의 정수를 한 줄에 출력한다. $1 \le i \le d$에 대해 $i$번째 수는 입력의 $i$번째 네트워크와 동등한 네트워크 중 가장 작은 번호 $j$여야 한다.