Description

Z-Kingdom has a well-connected modern transportation network. During the independence celebration, as the number of visitors from neighboring countries increases, criminal activities have quietly begun to rise.

The police officers of the Special Task Support Division received a request from headquarters to investigate criminals disguised as tourists. Through their investigation, they obtained a map recording the length of every road in Z-Kingdom.

Clearly, to reduce the chances of being discovered, criminals will always choose the shortest route for their movements. To better allocate manpower and predict the routes criminals might take, they want to know, for any two locations, how many routes the criminals might choose, i.e., how many shortest paths there are between them.

Input Format

The first line contains two integers $N, M$, representing the number of locations and the number of roads in Z-Kingdom.

The next $M$ lines, each containing three integers $x, y, z$, represent a bidirectional road connecting two different locations $x$ and $y$ with length $z$.

There is at most one road between any two different locations.

Output Format

Output one line containing $\dfrac{N(N-1)}{2}$ integers: $C_{1,2}, C_{1,3}, \cdots, C_{1,N}, C_{2,3}, C_{2,4}, \cdots, C_{2,N}, \cdots, C_{N-1,N}$, separated by spaces.

Here $C_{x, y}$ denotes the number of shortest paths from location $x$ to location $y$.

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

1 4 1 2 1 5 6 1 2 1

Hint

Constraints

• For $30\%$ of the testdata, $N \le 50$.
• For $60\%$ of the testdata, $N \le 100$.
• For $100\%$ of the testdata, $N \le 500$.

Translated by ChatGPT 5