结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

新区规划有 $n$ 个片区，编号为 $1$ 到 $n$。规划部门登记了 $m$ 条候选光缆线路，第 $i$ 条线路连接片区 $u_i$ 与片区 $v_i$，建设费用为 $w_i$。同一片区对之间可能登记多条不同的线路，但没有线路的两端连接同一片区。所有片区都能通过候选线路互相到达。

管委会要据此确定一套建设方案：从候选线路中选出若干条，使得任意两个片区都能通过选中的线路互相到达，且选中线路的建设费用总和最小。满足条件的方案称为最小费用方案；最小费用方案可能不止一套，它们的费用总和相同。

审计部门现在要对每条候选线路做分级：若每一个最小费用方案都选中该线路，将其标记为 2；若存在某个最小费用方案选中该线路，但并非每一个最小费用方案都选中它，将其标记为 1；若任何最小费用方案都不选中该线路，将其标记为 0。

请按输入顺序对每条候选线路给出它的审计标记。

输入格式

从文件 crucial.in 中读入数据。

• 第一行两个整数 $n, m$，表示片区数量与候选线路数量；
• 接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，依次描述每条候选线路连接的两个片区与建设费用。

输出格式

输出到文件 crucial.out 中。

输出 $m$ 行，第 $i$ 行一个整数 0、1 或 2，表示第 $i$ 条候选线路的审计标记。

样例

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

1
2
2
1
0

样例 1 解释

最小费用方案的费用总和为 $6$。第 $4$ 条线路与第 $1$ 条线路连接同一片区对、费用相同：任取一套含第 $1$ 条的最小费用方案，把第 $1$ 条换成第 $4$ 条，连通性不变、费用总和仍为 $6$，故两条线路的标记都是 1。第 $5$ 条线路费用为 $5$：选中它的方案费用总和至少为 $5 + 1 + 2 = 8 > 6$，故标记为 0。

4 5
1 2 1
2 3 2
3 1 3
3 4 4
1 4 10

2
2
0
2
0

样例 2 解释

最小费用方案的费用总和为 $7$。第 $3$ 条线路费用为 $3$：选中它的方案费用总和至少为 $3 + 1 + 4 = 8 > 7$，故标记为 0。第 $4$ 条线路：不含它的方案只能经第 $5$ 条线路连接片区 $4$，费用总和至少为 $1 + 2 + 10 = 13 > 7$，故每一个最小费用方案都选中第 $4$ 条，标记为 2。

5 6
1 2 1
2 3 1
3 1 1
3 4 2
4 5 2
1 3 4

1
1
1
2
2
0

样例 3 解释

最小费用方案的费用总和为 $6$。第 $1$ 条线路：选中前三条线路中的第 $1$、$2$ 条与第 $4$、$5$ 条的方案费用为 $1 + 1 + 2 + 2 = 6$，含第 $1$ 条；换成选中第 $2$、$3$ 条的方案费用同样为 $6$，不含第 $1$ 条，故标记为 1。第 $6$ 条线路连接片区 $1$ 与 $3$、费用为 $4$，而两端之间已有费用为 $1$ 的线路可走：选中它的方案费用总和至少为 $4 + 1 + 2 + 2 = 9 > 6$，故标记为 0。

数据范围

对于所有测试数据，保证：

• $1 \le n \le 10^5$，$n - 1 \le m \le 2 \times 10^5$；
• $1 \le u_i, v_i \le n$，$u_i \ne v_i$；
• $1 \le w_i \le 10^9$；
• 所有片区都能通过候选线路互相到达。

各测试点的约束如下：

• 特殊性质 A：所有线路的建设费用互不相同。
• 特殊性质 B：$m = n$。