← 返回题目列表

AtCoder · arc052_c

C. 高桥君与神秘之路

中文机器翻译题面 查看原题

問題文

町 0 卡拉町 N-1 最多 有 N 个城镇。 这些是 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