Berland 由 $n$ 个城市组成，编号从 $1$ 到 $n$。城市 $1$ 是 Berland 的首都。城市之间有 $m$ 条双向道路。道路仅在城市处相交。任意两个城市之间最多只有一条道路，且没有道路连接城市自身。如果你沿第 $j$ 条道路向任意方向行驶，都需要支付等于 $c_j$ 的税费。仅使用给定的 $m$ 条道路，可以从首都到达任何城市。

你是某快递公司的首席执行官，公司总部位于首都。你的公司向 Berland 的每个城市运送不同的货物，因此对于每个城市，你都选择了一条从首都到该城市且总税费之和最小的路线。设 $d_k$ 为从首都到城市 $k$ 所选路线的总成本。

政府决定选择恰好一条道路（你不知道是哪一条）并提高其使用税费。因此，对于每一条道路，你都想知道如果这条道路的税费增加，会有多少个城市受到影响。如果税费增加后，你无法再选择一条总成本等于 $d_k$ 的路线，则称城市 $k$ 受到影响。

输入格式

第一行包含两个整数 $n$ 和 $m$：Berland 的城市数量和道路数量（$2 \le n \le 2 \cdot 10^5$，$n - 1 \le m \le 2 \cdot 10^5$）。

接下来的 $m$ 行，每行包含三个空格分隔的整数：$u_j$、$v_j$ 和 $c_j$（$1 \le u_j, v_j \le n$，$1 \le c_j \le 10^9$）。这意味着连接城市 $u_j$ 和 $v_j$ 的第 $j$ 条道路的初始税费为 $c_j$。

任意两个城市之间最多只有一条道路，且没有道路连接城市自身。保证可以仅使用给定的道路从首都到达每个城市。

输出格式

输出 $m$ 个整数，每行一个。第 $j$ 个整数表示因第 $j$ 条道路成本增加而受到影响的城市数量。

样例

样例输入 1

6 6
1 2 2
2 3 1
3 4 7
4 5 4
5 2 4
4 6 4

样例输出 1

5
1
0
0
1
1