AT_arc052_c [ARC052C] 高橋くんと不思議な道

高桥君与不可思议的道路

日本国存在 $N$ 个城镇，从 $0$ 到 $N-1$ 编号。它们由 $M$ 条双向道路连接。 道路分为 A 型和 B 型两种。 沿 A 型道路行驶的成本为 1。 B 型道路的成本为（迄今为止走过的 B 型道路的数量）+1。 第 $i$ 条道路连接 $A_i$ 镇和 $B_i$ 镇，如果 $C_i$ 为 $0$，则属于 A 型道路；如果 $C_i$ 为 $1$，则属于 B 型道路。 对于所有城镇，分别求出从城镇 $0$ 到该城镇的最小旅行成本。 不存在无法从城镇 $0$ 到达的城镇。

第一行两个数 $N$ 与 $M$。 而后 $M$ 行，每行三个整数，分别是 $C_i,A_i,B_i$。

包括 $N$ 行。在第 $i$ 行，输出从城镇 $0$ 到城镇 $i-1$ 的移动成本。

给出的所有数字都是整数。 $1 \le N \le 10^4$，$1 \le M \le 10^5$，$0 \le A_i,B_i \le N-1$，$C_i \mathbb \in \{0,1\}$。