The mayor of Farzville is studying the city's road system to find ways of improving its traffic conditions. Farzville's road system consists of $n$ junctions connected by $\boldsymbol{\mathrm{~e~}}$ bidirectional toll roads, where the $i^{\mbox{th}}$ toll road connects junctions $x_i$ and $y_i$. In addition, some junctions may not be reachable from others and there may be multiple roads connecting the same pair of junctions.

Each toll road has a toll rate that's paid each time it's used. This rate varies depending on the direction of travel:

If traveling from $x_i$ to $y_i$, then the toll rate is $r_i$.
If traveling from $y_i$ to $x_i$, then the toll rate is $1000-r_i$. It is guaranteed that $0<r_i<1000$.

For each digit $d\in\{0,1,\ldots,9\}$, the mayor wants to find the number of ordered pairs of $(x,y)$ junctions such that $x\neq y$ and a path exists from $\boldsymbol{x}$ to $y$ where the total cost of the tolls (i.e., the sum of all toll rates on the path) ends in digit $\boldsymbol{d}$. Given a map of Farzville, can you help the mayor answer this question? For each digit $\boldsymbol{d}$ from $0$ to $\mbox{9}$, print the the number of valid ordered pairs on a new line.

Note: Each toll road can be traversed an unlimited number of times in either direction.

Input Format

The first line contains two space-separated integers describing the respective values of $n$ (the number of junctions) and $\boldsymbol{\mathrm{~e~}}$ (the number of roads).

Each line $\boldsymbol{i}$ of the $\boldsymbol{\mathrm{~e~}}$ subsequent lines describes a toll road in the form of three space-separated integers, $x_i$, $y_i$, and $r_i$.

Constraints

$1\leq n\leq10^5$
$1\leq e\leq2\cdot10^5$
$1\leq x_i,y_i\leq n$
$x_i\neq y_i$
$0<r_i<1000$

Output Format

Print ten lines of output. Each line $j$ (where $0\leq j\leq9$) must contain a single integer denoting the answer for $d=j$. For example, the first line must contain the answer for $\boldsymbol{d}=0$, the second line must contain the answer for $\boldsymbol{d}=1$, and so on.

Sample Input 0
3 3
1 3 602
1 2 256
2 3 411

Sample Output 0
0
2
1
1
2
0
2
1
1
2

Explanation 0

The table below depicts the distinct pairs of junctions for each $\boldsymbol{d}$:

$\begin{array}{cccc}d&(x,y)&\text{partial} &\text{total\quad cost}\\ \hline0&\text{none}&\\ \hline1&(1,2)&1\rightarrow3\rightarrow2&1191\\\quad &(2,3)&2\rightarrow3&411\\ \hline2&(1,3)&1\rightarrow3&602\\ \hline3&(3,1)&3\rightarrow2\rightarrow1&1333\\ \hline4&(2,1)&2\rightarrow1&744\\\quad &(3,2)&3\rightarrow1\rightarrow2&654\\ \hline5&\text{none} \\ \hline6&(1,2)&1\rightarrow2&256\\\quad &(2,3)&2\rightarrow1\rightarrow3&1346\\ \hline 7&(1,3)&1\rightarrow2\rightarrow3&667\\ \hline8&(3,1)&3\rightarrow1&398\\ \hline9&(2,1)&2\rightarrow3\rightarrow1&809\\\quad &(3,2)&3\rightarrow2&589\\ \hline\end{array}$

Note the following:

There may be multiple paths between each pair of junctions.
Junctions and roads may be traversed multiple times. For example, the path $2\to3\to1\to2\to3$ is also valid, and it has total cost of $411+398+256+411=1476$.
An ordered pair can be counted for more than one $\boldsymbol{d}$. For example, the pair $(2,3)$ is counted for $\boldsymbol{d}=1$ and $\boldsymbol{d=6}$.
Each ordered pair must only be counted once for each $\boldsymbol{d}$. For example, the paths $2\rightarrow1\rightarrow3$ and $2\to3\to1\to2\to3$ both have total costs that end in $\boldsymbol{d=6}$, but the pair $(2,3)$ is only counted once.

见题面

见题面