Problem Description

Xiao Lan is an employee of a communication network company, and he is doing some statistics work.

The communication network consists of $n$ relay stations and $m$ communication links. Transmitting information through one link takes a certain amount of time. If information is transmitted from one relay station to another through several links, the total delay is the sum of the time costs of all links. Since the capacity of a link is limited, suppose a link connects relay stations $x$ and $y$. If it takes time $w$ to transmit information from $x$ to $y$, then it takes time $20 - w$ to transmit information from $y$ to $x$.

Xiao Lan only cares about the ones digit of the total delay. For an ordered pair of different relay stations $(u, v)$, if information can be transmitted from $u$ to $v$ through several links, and the ones digit of the total delay is $k$, then Xiao Lan calls $(u, v)$ $k$-harmonious. Since the delay from $u$ to $v$ may differ from the delay from $v$ to $u$, $(u, v)$ and $(v, u)$ should be considered different relay-station pairs, and pairs like $(u, u)$ are invalid.

Now, Xiao Lan wants you to help him find how many relay-station pairs are 0-harmonious, 1-harmonious, 2-harmonious, $\ldots$, 9-harmonious.

Input Format

The input contains multiple lines. The first line contains two positive integers $n, m$, representing the number of relay stations and the number of links.

The next $m$ lines each contain three positive integers $x_i, y_i, w_i$, meaning there is a link between relay stations $x_i$ and $y_i$, and transmitting information along this link from $x_i$ to $y_i$ takes time $w_i$; transmitting from $y_i$ to $x_i$ takes time $20 - w_i$.

The given network may contain multiple edges or self-loops.

Output Format

Output a total of 10 lines. Each line contains one positive integer, representing the number of 0-harmonious, 1-harmonious, $\ldots$, 9-harmonious relay-station pairs, in order.

3 3
1 2 1
2 3 2
3 1 2

0
1
2
2
1
0
1
2
2
1

Hint

Sample Explanation

The table above lists the relay-station pairs that are $x$-harmonious. For example, there exists a communication route $1 \to 2 \to 3 \to 1 \to 2$ whose total delay is $6$, and the ones digit is $6$, so the pair $(1,2)$ is 6-harmonious.

A relay-station pair may be both $x$-harmonious and $y$-harmonious for different $x$ and $y$. For one relay-station pair, there may be multiple communication routes whose total delay has ones digit $x$, but it should only be counted once. For example, the total delay of $1 \to 3 \to 2$ is $16$, which also has ones digit $6$, but $(1,2)$ is counted only once among the 6-harmonious pairs.

Constraints and Notes for Test Cases

For $30\%$ of the data, $w_i = 10$.

For another $20\%$ of the data, $m = n - 1, x_i = i, y_i = i + 1$.

For another $20\%$ of the data, $m = n - 1$ and any two relay stations can definitely transmit information through links.

For $100\%$ of the data, $2 \leq n \leq 100000, 0 \leq m \leq 200000, 1 \leq x_i, y_i \leq n, 1 \leq w_i < 20$.

Translated by ChatGPT 5