你正计划建造一个输水管道网络，连接 KAIST 的 $n$ 栋建筑物。由于预算问题，你只能使用 $n - 1$ 条管道。每条管道都是无向的，连接两栋不同的建筑物，且所有 $n$ 栋建筑物必须通过某种管道序列两两连通。这些管道构成了一个网络。

作为一个细心的规划者，你设计了 $d$ 个不同的网络并希望对它们进行比较。网络中的每条管道都可以用一个正整数耐用度（durability）来描述。给定一个网络 $T$，定义两栋不同建筑物 $i$ 和 $j$ 之间的脆弱度（vulnerability）$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$ 个数应当是最小的索引 $j$，使得输入中的第 $j$ 个网络与第 $i$ 个网络等价。

样例

输入样例 1

3 3
1 2 1
1 3 1
1 2 1
2 3 1
1 2 1
2 3 2

输出样例 1

1 1 3

输入样例 2

3 4
1 2 2
2 3 1
3 4 2
1 3 2
2 4 2
2 3 1
1 2 2
1 3 1
3 4 2

输出样例 2

1 2 1