题目描述

小蓝是一家通信网络公司的工作人员，他正在进行统计工作。

通信网络由 $n$ 个中继站和 $m$ 条通信链路构成，信息通过一条链路需要花费一定的时间，信息从一个中继站经过若干条链路传输到另一个中继站，总延迟是各链路的花费时间之和。由于一条链路的容量有限，假设一条链路连接中继站 $x$ 和 $y$，如果信息从 $x$ 传递到 $y$ 花费时间 $w$，那么信息从 $y$ 传递到 $x$ 则需花费时间 $20 - w$。

小蓝只关心总延迟的个位数字是多少。对于一对不同的中继站对 $(u, v)$，如果信息能够通过若干条链路从 $u$ 传输到 $v$，且总延迟的个位数字是 $k$，则小蓝称 $(u, v)$ 是 $k$ 和谐的。由于从 $u$ 到 $v$ 的延迟和从 $v$ 到 $u$ 的延迟可能不同，$(u, v)$ 和 $(v, u)$ 应当认为是不同的中继站对，且像 $(u, u)$ 这样的中继站对是不合法的。

现在，小蓝希望你帮他求出，0 和谐，1 和谐，2 和谐，…，9 和谐的中继站对各有多少个。

输入格式

输入包含若干行，第一行两个正整数 $n, m$，分别表示中继站个数和链路条数。

接下来 $m$ 行，每行三个正整数 $x_i, y_i, w_i$，表示中继站 $x_i, y_i$ 之间有一条链路，且信息从这条链路上从 $x_i$ 传递到 $y_i$ 需要时间 $w_i$；从 $y_i$ 传递到 $x_i$ 需要时间 $20 - w_i$。

给定的网络可能包含重边或自环。

输出格式

输出共 10 行，每行一个正整数，依次表示 0 和谐，1 和谐，…，9 和谐的中继站对的数量。

3 3
1 2 1
2 3 2
3 1 2

0
1
2
2
1
0
1
2
2
1

提示

【样例说明】

上表列出了各个 $x$ 和谐的中继站对，例如存在一种通信方案 $1 \to 2 \to 3 \to 1 \to 2$ 的总延迟是 $6$，个位数是 $6$，所以点对 $(1,2)$ 是 $6$ 和谐的。

一个中继站对对于不同的 $x$ 和 $y$，可能既是 $x$ 和谐的，又是 $y$ 和谐的。对于一个中继站对，可能有多种通信方案的总延迟个位数都为 $x$，但应当只被统计一次，例如 $1 \to 3 \to 2$ 的总延迟是 $16$，也满足个位数是 $6$，但 $(1,2)$ 在 $6$ 和谐中只被统计一次。

【评测用例规模与约定】

对于 $30\%$ 的数据，$w_i = 10$；

对于另 $20\%$ 的数据，$m = n - 1, x_i = i, y_i = i + 1$；

对于另 $20\%$ 的数据，$m = n - 1$ 且任意两个中继站之间都一定能通过链路传输信息；

对于 $100\%$ 的数据，$2 \leq n \leq 100000, 0 \leq m \leq 200000, 1 \leq x_i, y_i \leq n, 1 \leq w_i < 20$。