有一个包含 n 个点，m 条边的无向图，第 i 条边的边权为 c_i，没有重边和自环。设 s_i 表示从结点 1 出发到达结点 i 的最短路的不同路径数 ( i ∈ [1, n] )， 显然可以通过删除若干条边使得 s_i = 1，也就是有且仅有一条从 1 到 i 的最短路，且保持最短路的路径长度不变，对于每个 i ，求出删除边数的最小值。

输入的第一行包含两个正整数 n, m。 

接下来 m 行，每行包含三个正整数 u_i , v_i , c_i 表示第 i 条边连接的两个点的编号和边权。 

输出 n 行，第 i 行包含一个正整数表示对于结点 i ，删除边数的最小值， 如果 1 和 i 不连通，输出 −1 。 

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

0
0
0
1

在给定的图中，只有 s₄ 一开始为 2，因为有两条最短路：1 → 2 → 4, 1 → 3 → 4，任意删掉一条边后，就可以只剩一条最短路。 

对于 30% 的评测用例，n ≤ 1000； 对于所有评测用例，n ≤ 10⁵ ，0 ≤ m ≤ min{ n(n−1)/2 , 10⁶ } ，1 ≤ u_i , v_i ≤ n ， 1 ≤ c_i ≤ 10 。