问题文档

有 $N$ 个城镇，从城镇 $0$ 到城镇 $N-1$。这些城镇之间通过 $M$ 条双向道路连接。

道路分为 $A$ 类型和 $B$ 类型。经过 $A$ 类型的道路需要花费 $1$ 单位的代价。经过 $B$ 类型的道路时，代价为 (之前经过的 $B$ 类型道路数量)$+1$。

其中，第 $i$ 条道路 ($1 ≤ i ≤ M$) 连接了城镇 $A_i$ 和城镇 $B_i$，当 $C_i = 0$ 时为 $A$ 类型，当 $C_i = 1$ 时为 $B$ 类型。

请求出从城镇 $0$ 到每个城镇的最小移动代价。

假设无法从城镇 $0$ 到达的城镇不存在。

约束条件

• 所给数字均为整数。
• $1 ≤ N ≤ 10^4$。
• $1 ≤ M ≤ 10^5$。
• $0 ≤ A_i, B_i ≤ N - 1$。
• $0 ≤ C_i ≤ 1$。

输入

输入通过标准输入给出，格式如下：

$N$ $M$ $C_1$ $A_1$ $B_1$ $C_2$ $A_2$ $B_2$ ： $C_M$ $A_M$ $B_M$

输出

输出为 $N$ 行。第 $i$ 行 ($1 ≤ i ≤ N$) 输出从城镇 $0$ 到城镇 $i-1$ 需要的最小代价。

示例1

3 3
0 0 1
1 1 2
1 2 0

输出示例1

0
1
1

示例2

7 8
1 0 1
1 1 2
1 2 5
1 5 6
0 1 3
0 3 4
0 4 5
0 2 6

输出示例2

0
1
3
2
3
4
4

示例3

8 9
0 0 1
0 1 2
0 2 3
0 5 6
0 6 7
1 1 3
1 3 4
1 4 5
1 5 7

输出示例3

0
1
2
2
4
6
7
8