有一个包含 n 个点，m 条边的无向图，第 i 条边的边权为 ci，没有重边和自环。设 si 表示从结点 1 出发到达结点 i 的最短路的不同路径数 ( i ∈ [1, n] )， 显然可以通过删除若干条边使得 si = 1，也就是有且仅有一条从 1 到 i 的最短路，且保持最短路的路径长度不变，对于每个 i ，求出删除边数的最小值。
输入的第一行包含两个正整数 n, m。
接下来 m 行，每行包含三个正整数 ui , vi , ci 表示第 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
在给定的图中，只有 s4 一开始为 2，因为有两条最短路：1 → 2 → 4, 1 → 3 → 4，任意删掉一条边后，就可以只剩一条最短路。
对于 30% 的评测用例，n ≤ 1000； 对于所有评测用例，n ≤ 105 ，0 ≤ m ≤ min{ n(n−1)/2 , 106 } ，1 ≤ ui , vi ≤ n ， 1 ≤ ci ≤ 10 。