19335번 - Increasing Costs 다국어

문제

Berland consists of $n$ cities labeled from 1ドル$ to $n$. The city number 1ドル$ is the capital of Berland. There are $m$ two-way roads between some cities. Roads can intersect only in cities. There is no more than one road between each pair of cities, and there is no road that connects a city to itself. If you are moving by $j$-th road in any direction, you have to pay the tax equal to $c_j$. It is possible to reach any city from the capital using only the given $m$ roads.

You are the CEO of a delivery company, its main office is located in the capital. Your company delivers different goods to every city of Berland, so for each city, you chose some route from the capital to that city which minimized the total sum of taxes of all roads in the route. Let $d_k$ be the total cost of the chosen route from the capital to city $k$.

The government has decided to choose exactly one road (you don't know which one) and increase the tax for using it. So, for each road, you want to know how many cities will be affected if the tax for using this road is increased. City $k$ is affected if, after the tax is increased, you can't choose a route such that the total cost of this route is equal to $d_k$.

입력

The first line contains two integers $n$ and $m$: the number of cities and the number roads in Berland (2ドル \le n \le 2 \cdot 10^{5},ドル $n - 1 \le m \le 2 \cdot 10^{5}$).

Each of the next $m$ lines contains three space-separated integers: $u_j,ドル $v_j,ドル and $c_j$ (1ドル \le u_j, v_j \le n,ドル 1ドル \le c_j \le 10^{9}$). These mean that the road number $j$ between cities $u_j$ and $v_j$ initially has tax equal to $c_j$.

There is no more than one road between each pair of cities, and there is no road that connects a city to itself. It is guaranteed that it is possible to reach every city from the capital using the given roads.

출력

Print $m$ integers, one per line. The $j$-th integer must be the number of cities affected by increasing the cost of $j$-th road.

제한

힌트