Parade

A city has $N$ intersections and $M$ roads. The intersections are numbered $0$ through $N-1$ and the roads are numbered $0$ through $M-1$. Every road is bidirectional and joins two different intersections. At most one road joins any given pair of intersections. The city is connected, so you can travel from any intersection to any other one along roads.

The mayor picks one road and holds a parade on it. While the parade runs, nobody can travel along that road.

The city runs one bus line for every pair of intersections $(X, Y)$, so there are $N(N-1)/2$ lines. A line is affected by the parade when the shortest distance between $X$ and $Y$ in the graph without the parade road is longer than the original shortest distance. A pair that can no longer reach each other counts as affected.

For each road, count the bus lines that are affected when the parade is held on that road.

The first line contains the number of intersections $N$ ($1 \le N \le 100$) and the number of roads $M$ ($1 \le M \le 2000$).

Each of the next $M$ lines describes one road, given in order from road $0$ to road $M-1$. A road is three integers from, to and time, meaning that traveling between intersection from and intersection to takes time. Both endpoint numbers are between $0$ and $N-1$ and are different, and the travel time is between $1$ and $1000$.

Print, for road $0$ through road $M-1$ in order, the number of bus lines affected when the parade is held on that road. Separate the numbers with spaces and print them on one line.