给定一个包含 $N$ 个顶点和 $M$ 条边的无向简单连通图 $G$。图 $G$ 的顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。

给定一个长度为 $M$ 的序列 $C = (c_1, c_2, \dots, c_M)$，由 $0$ 和 $1$ 组成。当 $c_i = 0$ 时，第 $i$ 条边被涂成蓝色；当 $c_i = 1$ 时，第 $i$ 条边被涂成红色。边的颜色满足：恰好有 $N - 1$ 条红色边，且它们构成了 $G$ 的一棵生成树。

请找到字典序最小的排列 $P = (p_1, p_2, \dots, p_M)$，使得满足以下条件：若对于每个 $i$，第 $i$ 条边的权重为 $p_i$，则 $G$ 的最小生成树中使用的所有边均为红色。

注意，在该条件下，$G$ 的最小生成树是唯一确定的。

输入格式

第一行包含两个整数 $N$ 和 $M$：分别为图 $G$ 的顶点数和边数（$2 \le N \le 2 \cdot 10^5$，$N - 1 \le M \le 2 \cdot 10^5$）。

接下来的 $M$ 行包含边的描述。每行包含三个整数 $a_i, b_i$ 和 $c_i$（$1 \le a_i, b_i \le N, 0 \le c_i \le 1$）：表示该边连接的顶点以及边的颜色（若 $c_i = 1$ 则为红色，否则为蓝色）。

你可以假设图中没有重边和自环，给定的图是连通的，且红色边构成了该图的一棵生成树。

输出格式

输出 $M$ 个整数，构成满足以下条件的字典序最小的排列 $P$：若对于每个 $i$，第 $i$ 条边的权重为 $p_i$，则 $G$ 的最小生成树中使用的所有边均为红色。

样例

输入 1

4 5
1 2 0
2 3 1
3 4 1
2 4 0
1 3 1

输出 1

3 1 4 5 2