L. Increasing Costs
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

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 cj. 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 dk 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 dk.

Input

The first line contains two integers n and m: the number of cities and the number roads in Berland (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105).

Each of the next m lines contains three space-separated integers: uj, vj, and cj (1 ≤ uj, vj ≤ n, 1 ≤ cj ≤ 109). These mean that the road number j between cities uj and vj initially has tax equal to cj.

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.

Output

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.

Example
Input
6 6
1 2 2
2 3 1
3 4 7
4 5 4
5 2 4
4 6 4
Output
5
1
0
0
1
1