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.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Graph algorithms


Solutions:
from collections import deque
from collections import defaultdict
(n, e) = [int(x) for x in input().split()]
kop = defaultdict(set)
gran = defaultdict(list)
for _ in range(e):
	(x, y, k) = [int(x) for x in input().split()]
	kop[x - 1, y - 1].add(k % 10)
	kop[y - 1, x - 1].add(10 - k % 10)
	gran[x - 1].append(y - 1)
	gran[y - 1].append(x - 1)
out = [0] * 10
founder = [[0] * n for _ in range(10)]
found = [False] * n
for i in range(n):
	if found[i]:
		continue
	que = deque()
	que.append((i, 0))
	cluster = set()
	while len(que) > 0:
		(j, col) = que.pop()
		if founder[col][j] == 1:
			continue
		founder[col][j] = 1
		found[j] = True
		cluster.add(j)
		for k in gran[j]:
			for kost in kop[j, k]:
				que.append((k, (kost + col) % 10))
	if founder[1][i] == 1:
		cycle = 1
		for d in range(10):
			out[d] += len(cluster) * (len(cluster) - 1)
	elif founder[2][i] == 1:
		cycle = 2
	elif founder[5][i] == 1:
		cycle = 5
	else:
		cycle = 0
	firstc = [set() for _ in range(10)]
	for node in cluster:
		for ind in range(10):
			if founder[ind][node] == 1:
				firstc[ind].add(node)
				break
	dig = [0] * 10
	for d1 in range(10):
		for d2 in range(10):
			if d1 != d2:
				dig[(d2 - d1) % 10] += len(firstc[d1]) * len(firstc[d2])
			else:
				dig[0] += len(firstc[d1]) * (len(firstc[d1]) - 1)
	if cycle == 2:
		summaEv = dig[0] + dig[2] + dig[4] + dig[6] + dig[8]
		for d in [0, 2, 4, 6, 8]:
			out[d] += summaEv
		summaOdd = dig[1] + dig[3] + dig[5] + dig[7] + dig[9]
		for d in [1, 3, 5, 7, 9]:
			out[d] += summaOdd
	elif cycle == 5:
		summa0 = dig[0] + dig[5]
		summa1 = dig[1] + dig[6]
		summa2 = dig[2] + dig[7]
		summa3 = dig[3] + dig[8]
		summa4 = dig[4] + dig[9]
		for d in [0, 5]:
			out[d] += summa0
		for d in [1, 6]:
			out[d] += summa1
		for d in [2, 7]:
			out[d] += summa2
		for d in [3, 8]:
			out[d] += summa3
		for d in [4, 9]:
			out[d] += summa4
	elif cycle == 0:
		for d in range(10):
			out[d] += dig[d]
for d in range(10):
	print(out[d])


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


from collections import deque, defaultdict
(n, e) = [int(x) for x in input().split()]
E = defaultdict(list)
for _ in range(e):
	(x, y, c) = [int(x) for x in input().split()]
	x -= 1
	y -= 1
	E[x].append((y, c % 10))
	E[y].append((x, -c % 10))
visited = [False] * n
colored = [[False] * n for _ in range(10)]
ways = [0] * 10
for i in range(n):
	if visited[i]:
		continue
	visited[i] = True
	cluster = {i}
	Q = deque()
	Q.append((i, 0))
	while Q:
		(cur, color) = Q.pop()
		if colored[color][cur]:
			continue
		colored[color][cur] = True
		visited[cur] = True
		cluster.add(cur)
		for (neigh, weight) in E[cur]:
			newcolor = (weight + color) % 10
			Q.append((neigh, newcolor))
	if colored[1][i]:
		cycle = 1
		nreachable = len(cluster) * (len(cluster) - 1)
		for d in range(10):
			ways[d] += nreachable
		continue
	elif colored[2][i]:
		cycle = 2
	elif colored[5][i]:
		cycle = 5
	else:
		cycle = 0
	rootdist = [set() for _ in range(10)]
	for node in cluster:
		for d in range(10):
			if colored[d][node]:
				rootdist[d].add(node)
				break
	dig = [0] * 10
	for a in range(10):
		for b in range(10):
			if a != b:
				dig[(b - a) % 10] += len(rootdist[a]) * len(rootdist[b])
			else:
				dig[0] += len(rootdist[a]) * (len(rootdist[a]) - 1)
	if cycle == 2:
		even = sum(dig[0::2])
		odd = sum(dig[1::2])
		for d in [0, 2, 4, 6, 8]:
			ways[d] += even
		for d in [1, 3, 5, 7, 9]:
			ways[d] += odd
	elif cycle == 5:
		sigma = [dig[0] + dig[5], dig[1] + dig[6], dig[2] + dig[7], dig[3] + dig[8], dig[4] + dig[9]]
		for d in range(10):
			ways[d] += sigma[d % 5]
	elif cycle == 0:
		for d in range(10):
			ways[d] += dig[d]
for d in range(10):
	print(ways[d])


import sys
import collections
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
adj = [[] for i in range(n)]
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x) - 1, int(y) - 1, int(r) % 10]
	adj[x].append([y, r])
	adj[y].append([x, (10 - r) % 10])
seen = [0] * n
toll = [0] * n

def bits(b):
	s = ''
	for i in range(10):
		s += ['0', '1'][b >> i & 1]
	return s
ans = [0] * 10
for src in range(n):
	if seen[src]:
		continue
	comp = []
	toll[src] = 1
	q = collections.deque()
	q.append(src)
	while len(q) > 0:
		c = q.popleft()
		if seen[c] == 0:
			seen[c] = 1
			comp.append(c)
		for a in adj[c]:
			(cc, t) = a
			tt = toll[c] << t
			tt = (tt | tt >> 10) & 1023
			if tt & ~toll[cc] != 0:
				toll[cc] |= tt
				q.append(cc)
	cn = len(comp)
	if cn < 2:
		continue
	cans = [0] * 10
	assert toll[src] == 1023 or toll[src] == 1 or toll[src] == 341 or (toll[src] == 33)
	B = 10
	if toll[src] == 33:
		B = 5
	if toll[src] == 341:
		B = 2
	if toll[src] == 1023:
		B = 1
	cnt = [0] * 10
	for c in comp:
		for b in range(B):
			if toll[c] >> b & 1:
				cnt[b] += 1
	for c in comp:
		for b in range(B):
			if toll[c] >> b & 1:
				for bb in range(B):
					cans[(bb + 10 - b) % B] += cnt[bb]
	cans[0] -= cn
	for b in range(10):
		ans[b] += cans[b % B]
for a in ans:
	print(a)


import sys
import itertools
from collections import deque
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for i in range(n):
	connections.append([])
costs = {}
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x) - 1, int(y) - 1, int(r)]
	connections[x].append(y)
	connections[y].append(x)
	cost1 = costs.get((x, y), set())
	cost1.add(r % 10)
	costs[x, y] = cost1
	cost2 = costs.get((y, x), set())
	cost2.add((1000 - r) % 10)
	costs[y, x] = cost2
subgraphs = []
todo = set()
for i in range(n):
	todo.add(i)
while len(todo):
	subgraph = set()
	seeds = []
	seeds.append(todo.pop())
	while len(seeds):
		seed = seeds.pop()
		subgraph.add(seed)
		todo.discard(seed)
		for neighbour in connections[seed]:
			if neighbour in todo:
				seeds.append(neighbour)
	subgraphs.append(subgraph)
totals = [0] * 10
for graph in subgraphs:
	possibletolls = {}
	startnode = -1
	for node in graph:
		possibletolls[node] = -1
		startnode = node
	seeds = set()
	seeds.add(startnode)
	possibletolls[startnode] = 0
	have2 = False
	have5 = False
	haveAll = False
	while len(seeds):
		seed = seeds.pop()
		tollsofar = possibletolls[seed]
		for neighbour in set(connections[seed]):
			tolls = costs[seed, neighbour]
			newtolls = itertools.product([tollsofar], tolls)
			newtolls = set([sum(x) % 10 for x in newtolls])
			if possibletolls[neighbour] != -1:
				newtolls.add(possibletolls[neighbour])
			roundtrips = set([(10 + x[0] - x[1]) % 10 for x in itertools.combinations(newtolls, 2)])
			for roundtrip in roundtrips:
				if roundtrip == 0:
					continue
				elif roundtrip == 5:
					have5 = True
				elif roundtrip % 2 == 0:
					have2 = True
				else:
					haveAll = True
			if possibletolls[neighbour] == -1:
				possibletolls[neighbour] = newtolls.pop()
				seeds.add(neighbour)
	summedtolls = [0] * 10
	for node in graph:
		summedtolls[possibletolls[node]] += 1
	for node in graph:
		temptolls = [x for x in summedtolls]
		owntoll = possibletolls[node]
		temptolls[owntoll] -= 1
		temptolls = deque(temptolls)
		temptolls.rotate(-owntoll)
		for i in range(10):
			totals[i] += temptolls[i]
		if haveAll or (have5 and have2):
			for j in range(9):
				temptolls.rotate(1)
				for i in range(10):
					totals[i] += temptolls[i]
		elif have5:
			temptolls.rotate(5)
			for i in range(10):
				totals[i] += temptolls[i]
		elif have2:
			for j in range(4):
				temptolls.rotate(2)
				for i in range(10):
					totals[i] += temptolls[i]
for x in totals:
	print(x)


from collections import deque
from collections import defaultdict
(n, e) = [int(x) for x in input().split()]
kop = defaultdict(set)
gran = defaultdict(list)
for _ in range(e):
	(x, y, k) = [int(x) for x in input().split()]
	kop[x - 1, y - 1].add(k % 10)
	kop[y - 1, x - 1].add(10 - k % 10)
	gran[x - 1].append(y - 1)
	gran[y - 1].append(x - 1)
out = [0] * 10
founder = [[0] * n for _ in range(10)]
found = [False] * n
for i in range(n):
	if found[i]:
		continue
	que = deque()
	que.append((i, 0))
	cluster = set()
	while len(que) > 0:
		(j, col) = que.pop()
		if founder[col][j] == 1:
			continue
		founder[col][j] = 1
		found[j] = True
		cluster.add(j)
		for k in gran[j]:
			for kost in kop[j, k]:
				que.append((k, (kost + col) % 10))
	if founder[1][i] == 1:
		cycle = 1
		for d in range(10):
			out[d] += len(cluster) * (len(cluster) - 1)
	elif founder[2][i] == 1:
		cycle = 2
	elif founder[5][i] == 1:
		cycle = 5
	else:
		cycle = 0
	firstc = [set() for _ in range(10)]
	for node in cluster:
		for ind in range(10):
			if founder[ind][node] == 1:
				firstc[ind].add(node)
				break
	dig = [0] * 10
	for d1 in range(10):
		for d2 in range(10):
			if d1 != d2:
				dig[(d2 - d1) % 10] += len(firstc[d1]) * len(firstc[d2])
			else:
				dig[0] += len(firstc[d1]) * (len(firstc[d1]) - 1)
	if cycle == 2:
		summaEv = dig[0] + dig[2] + dig[4] + dig[6] + dig[8]
		for d in [0, 2, 4, 6, 8]:
			out[d] += summaEv
		summaOdd = dig[1] + dig[3] + dig[5] + dig[7] + dig[9]
		for d in [1, 3, 5, 7, 9]:
			out[d] += summaOdd
	elif cycle == 5:
		summa0 = dig[0] + dig[5]
		summa1 = dig[1] + dig[6]
		summa2 = dig[2] + dig[7]
		summa3 = dig[3] + dig[8]
		summa4 = dig[4] + dig[9]
		for d in [0, 5]:
			out[d] += summa0
		for d in [1, 6]:
			out[d] += summa1
		for d in [2, 7]:
			out[d] += summa2
		for d in [3, 8]:
			out[d] += summa3
		for d in [4, 9]:
			out[d] += summa4
	elif cycle == 0:
		for d in range(10):
			out[d] += dig[d]
for d in range(10):
	print(out[d])


from collections import deque, defaultdict
(n, e) = [int(x) for x in input().split()]
E = defaultdict(list)
for _ in range(e):
	(x, y, c) = [int(x) for x in input().split()]
	x -= 1
	y -= 1
	E[x].append((y, c % 10))
	E[y].append((x, -c % 10))
visited = [False] * n
colored = [[False] * n for _ in range(10)]
ways = [0] * 10
for i in range(n):
	if visited[i]:
		continue
	visited[i] = True
	cluster = {i}
	Q = deque()
	Q.append((i, 0))
	while Q:
		(cur, color) = Q.pop()
		if colored[color][cur]:
			continue
		colored[color][cur] = True
		visited[cur] = True
		cluster.add(cur)
		for (neigh, weight) in E[cur]:
			newcolor = (weight + color) % 10
			Q.append((neigh, newcolor))
	if colored[1][i]:
		cycle = 1
		nreachable = len(cluster) * (len(cluster) - 1)
		for d in range(10):
			ways[d] += nreachable
		continue
	elif colored[2][i]:
		cycle = 2
	elif colored[5][i]:
		cycle = 5
	else:
		cycle = 0
	rootdist = [set() for _ in range(10)]
	for node in cluster:
		for d in range(10):
			if colored[d][node]:
				rootdist[d].add(node)
				break
	dig = [0] * 10
	for a in range(10):
		for b in range(10):
			if a != b:
				dig[(b - a) % 10] += len(rootdist[a]) * len(rootdist[b])
			else:
				dig[0] += len(rootdist[a]) * (len(rootdist[a]) - 1)
	if cycle == 2:
		even = sum(dig[0::2])
		odd = sum(dig[1::2])
		for d in [0, 2, 4, 6, 8]:
			ways[d] += even
		for d in [1, 3, 5, 7, 9]:
			ways[d] += odd
	elif cycle == 5:
		sigma = [dig[0] + dig[5], dig[1] + dig[6], dig[2] + dig[7], dig[3] + dig[8], dig[4] + dig[9]]
		for d in range(10):
			ways[d] += sigma[d % 5]
	elif cycle == 0:
		for d in range(10):
			ways[d] += dig[d]
for d in range(10):
	print(ways[d])


from collections import OrderedDict, deque
import sys
ENTER = 0
EXIT = 1

def read_line():
	return (int(x) for x in sys.stdin.readline().split())

def dfs1(g, depth, path_sum, dp, cycles, root):
	stack = deque([(ENTER, 0, root, 0)])
	while stack:
		(op, parent, v, p_cost) = stack.pop()
		if op == ENTER:
			if depth[v] != -1:
				continue
			stack.append((EXIT, parent, v, p_cost))
			depth[v] = depth[parent] + 1
			path_sum[v] = p_cost
			for n in g[v]:
				if depth[n] == -1:
					stack.append((ENTER, v, n, (p_cost + g[v][n][0]) % 10))
				elif depth[n] < depth[v]:
					for c in g[v][n]:
						p_sum = p_cost - path_sum[n] + c
						cycles[p_sum % 10] = True
		elif parent:
			pc = -g[parent][v][0] % 10
			dp[parent][pc] += 1
			for i in range(10):
				dp[parent][(i + pc) % 10] += dp[v][i]

def dfs2(g, visited, dp, root):
	stack = deque([(0, root)])
	while stack:
		(parent, v) = stack.pop()
		if v in visited:
			continue
		visited.add(v)
		if parent:
			pc = g[parent][v][0]
			dp[v] = [dp[parent][(i - pc) % 10] for i in range(10)]
			dp[v][0] -= 1
			dp[v][pc] += 1
		for child in g[v]:
			stack.append((v, child))
(n, e) = read_line()
g = [OrderedDict() for _ in range(n + 1)]
for _ in range(e):
	(x, y, r) = read_line()
	g[x].setdefault(y, set()).add(r % 10)
	g[y].setdefault(x, set()).add(-r % 10)
for v in range(1, n + 1):
	for neighbor in g[v]:
		g[v][neighbor] = sorted(g[v][neighbor])
depth = [-1] * (n + 1)
path_sum = [0] * (n + 1)
dp = [[0] * 10 for _ in range(n + 1)]
result = [0] * 10
for v in range(1, n + 1):
	if depth[v] != -1:
		continue
	cycles = [False] * 10
	dfs1(g, depth, path_sum, dp, cycles, v)
	visited = set()
	dfs2(g, visited, dp, v)
	component = [0] * 10
	for v2 in visited:
		for i in range(10):
			component[i] += dp[v2][i]
	even = any((cycles[i] for i in range(2, 10, 2)))
	odd = any((cycles[i] for i in range(1, 10, 2) if i % 5))
	odd = odd or (cycles[5] and even)
	for i in range(10):
		if odd:
			result[i] += sum(component)
		elif even:
			result[i] += sum((component[x] for x in range(i % 2, 10, 2)))
		elif cycles[5]:
			result[i] += component[i] + component[(i + 5) % 10]
		else:
			result[i] += component[i]
print('\n'.join((str(x) for x in result)))


(n, e) = map(int, input().strip().split())
adj = [[] for i in range(n)]
for ee in range(e):
	(a, b, c) = map(int, input().strip().split())
	a -= 1
	b -= 1
	adj[a].append((b, +c % 10))
	adj[b].append((a, -c % 10))
ovis = [False] * n
vis = [[False] * 10 for i in range(n)]
ans = [0] * 10
for s in range(n):
	if ovis[s]:
		continue
	queue = [(s, 0)]
	vis[s][0] = True
	f = 0
	ct = [0] * 10
	while f < len(queue):
		(i, d) = queue[f]
		f += 1
		ct[d] += 1
		for (j, nd) in adj[i]:
			nd = (nd + d) % 10
			if not vis[j][nd]:
				vis[j][nd] = True
				queue.append((j, nd))
	for (i, d) in queue:
		if ovis[i]:
			continue
		ovis[i] = True
		d = -d % 10
		for nd in range(10):
			ans[(nd + d) % 10] += ct[nd] - vis[i][nd]
for v in ans:
	print(v)


import math
import os
import random
import re
import sys
(n, e) = map(int, input().strip().split())
adj = [[] for i in range(n)]
for i in range(e):
	(x, y, r) = map(int, input().split())
	x -= 1
	y -= 1
	adj[x].append((y, +r % 10))
	adj[y].append((x, -r % 10))
visn = [False] * n
vis = [[False] * 10 for i in range(n)]
C = [[0] * 10 for i in range(n)]
D = [None] * n
for x in range(n):
	if visn[x]:
		continue
	stack = [(x, 0)]
	current = []
	vis[x][0] = True
	while stack:
		(xi, di) = stack.pop()
		if not visn[xi]:
			visn[xi] = True
			current.append(xi)
		C[x][di] += 1
		D[xi] = di
		for (xj, dj) in adj[xi]:
			dij = (di + dj) % 10
			if not vis[xj][dij]:
				vis[xj][dij] = True
				stack.append((xj, dij))
	for xi in current:
		for di in range(10):
			C[xi][di] = C[x][(di + D[xi]) % 10]
for di in range(10):
	ans = 0
	for xi in range(n):
		ans += C[xi][di] - vis[xi][(di + D[xi]) % 10]
	print(ans)


(n, e) = map(int, input().split())
adj = [[] for i in range(n)]
for i in range(e):
	(x, y, r) = map(int, input().split())
	x -= 1
	y -= 1
	adj[x].append((y, +r % 10))
	adj[y].append((x, -r % 10))
visn = [False] * n
vis = [[False] * 10 for i in range(n)]
C = [[0] * 10 for i in range(n)]
D = [None] * n
for x in range(n):
	if visn[x]:
		continue
	stack = [(x, 0)]
	current = []
	vis[x][0] = True
	while stack:
		(xi, di) = stack.pop()
		if not visn[xi]:
			visn[xi] = True
			current.append(xi)
		C[x][di] += 1
		D[xi] = di
		for (xj, dj) in adj[xi]:
			dij = (di + dj) % 10
			if not vis[xj][dij]:
				vis[xj][dij] = True
				stack.append((xj, dij))
	for xi in current:
		for di in range(10):
			C[xi][di] = C[x][(di + D[xi]) % 10]
for di in range(10):
	ans = 0
	for xi in range(n):
		ans += C[xi][di] - vis[xi][(di + D[xi]) % 10]
	print(ans)


(n, e) = map(int, input().strip().split())
adj = [[] for i in range(n)]
for ee in range(e):
	(a, b, c) = map(int, input().strip().split())
	a -= 1
	b -= 1
	adj[a].append((b, +c % 10))
	adj[b].append((a, -c % 10))
p = [False] * n
q = [[False] * 10 for i in range(n)]
ans = [0] * 10
for s in range(n):
	if p[s]:
		continue
	queue = [(s, 0)]
	q[s][0] = True
	f = 0
	ct = [0] * 10
	while f < len(queue):
		(i, d) = queue[f]
		f += 1
		ct[d] += 1
		for (j, nd) in adj[i]:
			nd = (nd + d) % 10
			if not q[j][nd]:
				q[j][nd] = True
				queue.append((j, nd))
	for (i, d) in queue:
		if p[i]:
			continue
		p[i] = True
		d = -d % 10
		for nd in range(10):
			ans[(nd + d) % 10] += ct[nd] - q[i][nd]
for v in ans:
	print(v)


import math
import itertools
from collections import defaultdict

def _normalize_toll(value):
	if value >= 0:
		return value
	return 10 + value

class Graph:

	def __init__(self, vertices_d, edges_d):
		self.vertices_d = vertices_d
		self.edges_d = edges_d

	@property
	def root(self):
		return self.vertices_d.get(1)

	@property
	def vertices(self):
		return list(self.vertices_d.values())

	def edges(self, vertex):
		edges = self.edges_d.get(vertex, [])
		adjacent = []
		for edge in edges:
			if edge.v1 == vertex:
				adjacent.append(edge)
		return adjacent

	@classmethod
	def create(cls, road_from, road_to, road_weight):
		vertices_d = {}
		edges_d = defaultdict(list)
		for i in range(len(road_from)):
			(src, dst, w) = (road_from[i], road_to[i], road_weight[i])
			src = vertices_d.setdefault(src, Vertex(src))
			dst = vertices_d.setdefault(dst, Vertex(dst))
			edge1 = Edge(src, dst, w)
			edge2 = Edge(dst, src, (1000 - w) % 10, is_reversed=True)
			(edge1.reversed_edge, edge2.reversed_edge) = (edge2, edge1)
			edges_d[src].append(edge1)
			edges_d[dst].append(edge2)
		return Graph(vertices_d, edges_d)

class Vertex:

	def __init__(self, id_):
		self.id = id_

	def __repr__(self):
		return f'{self.id}'

class Edge:

	def __init__(self, v1, v2, toll, is_reversed=False):
		self.v1 = v1
		self.v2 = v2
		self.toll = toll
		self.reversed_edge = None
		self.is_reversed = is_reversed

	def __repr__(self):
		return f'[{self.v1}->{self.v2}]'

def dfs(graph):
	to_visit = set(graph.vertices)
	visited_edges = set()
	visited_vertices = set()
	while to_visit:
		loops = set()
		tolls_by_digit = defaultdict(set)
		extras = defaultdict(set)
		root = to_visit.pop()
		tolls = {root: 0}
		stack = [root]
		while stack:
			vertex = stack.pop(0)
			if vertex in visited_vertices:
				continue
			visited_vertices.add(vertex)
			edges = graph.edges(vertex)
			for edge in edges:
				if edge in visited_edges:
					continue
				visited_edges.add(edge)
				next_v = edge.v2
				toll = _normalize_toll((tolls[vertex] + edge.toll) % 10)
				if next_v in tolls:
					loop_toll = _normalize_toll((toll - tolls[next_v]) % 10)
					if loop_toll != 0:
						loops.add(loop_toll)
					if next_v != root:
						extras[next_v].add(toll)
				else:
					if next_v in to_visit:
						tolls_by_digit[toll].add(next_v)
						to_visit.remove(next_v)
					tolls[next_v] = toll
					stack.insert(0, next_v)
		yield (tolls_by_digit, extras, loops)

def main(road_from, road_to, road_weight):
	graph = Graph.create(road_from, road_to, road_weight)
	result = defaultdict(int)
	reversed_tolls = defaultdict(int)
	for (root_tolls_by_digit, extras, loops) in dfs(graph):
		tree_result = defaultdict(int)
		for d1 in range(10):
			sources = root_tolls_by_digit[d1]
			if not sources:
				continue
			if len(sources) > 1:
				tree_result[0] += math.factorial(len(sources)) // math.factorial(2) // math.factorial(len(sources) - 2)
			tree_result[d1] += len(sources)
			for d2 in range(d1 + 1, 10):
				destinations = root_tolls_by_digit[d2]
				if d1 == d2 or not destinations:
					continue
				toll = _normalize_toll((d2 - d1) % 10)
				tree_result[toll] += len(sources) * len(destinations)
		loops_filtered = set()
		result_cache = tree_result.copy()
		for loop_cost in loops:
			for i in range(0, 100, loop_cost):
				if i == 0:
					continue
				if i % 10 == 0:
					break
				loops_filtered.add(i % 10)
		for (d1, d2) in itertools.product(loops_filtered, loops_filtered):
			if d1 == d2:
				continue
			new_digit = (d1 + d2) % 10
			if new_digit != 0:
				loops_filtered.add(new_digit)
		for loop_cost in loops_filtered:
			for digit in list(tree_result.keys()):
				if not tree_result[digit]:
					continue
				new_digit = (digit + loop_cost) % 10
				tree_result[new_digit] += result_cache[digit]
		for digit in list(tree_result.keys()):
			result[digit] += tree_result[digit]
			reversed_tolls[(10 - digit) % 10] += tree_result[digit]
	for i in range(10):
		print(f'{result[i] + reversed_tolls[i]}')
(road_nodes, road_edges) = map(int, input().split())
road_from = [0] * road_edges
road_to = [0] * road_edges
road_weight = [0] * road_edges
for i in range(road_edges):
	(road_from[i], road_to[i], road_weight[i]) = map(int, input().split())
main(road_from, road_to, road_weight)


(n, e) = map(int, input().strip().split())
adj = [[] for i in range(n)]
for ee in range(e):
	(a, b, c) = map(int, input().strip().split())
	a -= 1
	b -= 1
	adj[a].append((b, +c % 10))
	adj[b].append((a, -c % 10))
p = [False] * n
q = [[False] * 10 for i in range(n)]
ans = [0] * 10
for s in range(n):
	if p[s]:
		continue
	queue = [(s, 0)]
	q[s][0] = True
	f = 0
	ct = [0] * 10
	while f < len(queue):
		(i, d) = queue[f]
		f += 1
		ct[d] += 1
		for (j, nd) in adj[i]:
			nd = (nd + d) % 10
			if not q[j][nd]:
				q[j][nd] = True
				queue.append((j, nd))
	for (i, d) in queue:
		if p[i]:
			continue
		p[i] = True
		d = -d % 10
		for nd in range(10):
			ans[(nd + d) % 10] += ct[nd] - q[i][nd]
for v in ans:
	print(v)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import math
import os
import random
import re
import sys
import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import math
import os
import random
import re
import sys
import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import math
import os
import random
import re
import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import math
import os
import random
import re
import sys
import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import math
import os
import random
import re
import sys
import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(poker, e) = input().strip().split(' ')
(poker, e) = [int(poker), int(e)]
kinguu = []
for a0 in range(e):
	(kgf, rrr, rade) = input().strip().split(' ')
	(kgf, rrr, rade) = [int(kgf), int(rrr), int(rade)]
	kinguu.append([kgf - 1, rrr - 1, rade % 10])
nNodes = poker
visss = e
footss = {m: [] for m in range(nNodes)}
for ullu in kinguu:
	footss[ullu[0]].append((ullu[1], ullu[2]))
	footss[ullu[1]].append((ullu[0], (10 - ullu[2]) % 10))
suus = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def jiljiga(Comb):
	Out = [0 for m in range(10)]
	for ullu in Comb[0]:
		for i2 in Comb[1]:
			Out[(ullu - i2) % 10] = 1
	return Out
while len(suus) > 0:
	pogoo = set()
	StartNode = suus.pop()
	pogoo.add(StartNode)
	StartIterList = []
	for ullu in footss[StartNode]:
		if ullu[1] not in TollSumFromZero[ullu[0]]:
			TollSumFromZero[ullu[0]].add(ullu[1])
			StartIterList.append(ullu)
	SIListNew = []
	while len(StartIterList) > 0:
		for ullu in StartIterList:
			if ullu[0] in suus:
				suus.remove(ullu[0])
				pogoo.add(ullu[0])
			for i2 in footss[ullu[0]]:
				NewTollDig = (ullu[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in pogoo:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = jiljiga(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for ullu in range(10):
				MasterOut[ullu] += MultFactor * CD[ullu]
for (I1, ullu) in enumerate(MasterOut):
	print(ullu)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def setpair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	newlist = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					newlist.append((i2[0], NewTollDig))
		StartIterList = newlist
		newlist = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = setpair(Comb)
		factormulti = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			factormulti -= SubgraphDict1[Comb[0]]
		if factormulti > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += factormulti * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)


import sys
import itertools as it
(n, e) = input().strip().split(' ')
(n, e) = [int(n), int(e)]
connections = []
for a0 in range(e):
	(x, y, r) = input().strip().split(' ')
	(x, y, r) = [int(x), int(y), int(r)]
	connections.append([x - 1, y - 1, r % 10])
nNodes = n
nCon = e
Paths = {m: [] for m in range(nNodes)}
for i1 in connections:
	Paths[i1[0]].append((i1[1], i1[2]))
	Paths[i1[1]].append((i1[0], (10 - i1[2]) % 10))
StartNodeSet = set([m for m in range(nNodes)])
TollSumFromZero = {m: set() for m in range(nNodes)}
CombDict = {}
MasterOut = [0 for m in range(10)]

def CombineSetPair(Comb):
	Out = [0 for m in range(10)]
	for i1 in Comb[0]:
		for i2 in Comb[1]:
			Out[(i1 - i2) % 10] = 1
	return Out
while len(StartNodeSet) > 0:
	SubGraphNodes = set()
	StartNode = StartNodeSet.pop()
	SubGraphNodes.add(StartNode)
	StartIterList = []
	for i1 in Paths[StartNode]:
		if i1[1] not in TollSumFromZero[i1[0]]:
			TollSumFromZero[i1[0]].add(i1[1])
			StartIterList.append(i1)
	SIListNew = []
	while len(StartIterList) > 0:
		for i1 in StartIterList:
			if i1[0] in StartNodeSet:
				StartNodeSet.remove(i1[0])
				SubGraphNodes.add(i1[0])
			for i2 in Paths[i1[0]]:
				NewTollDig = (i1[1] + i2[1]) % 10
				if NewTollDig not in TollSumFromZero[i2[0]]:
					TollSumFromZero[i2[0]].add(NewTollDig)
					SIListNew.append((i2[0], NewTollDig))
		StartIterList = SIListNew
		SIListNew = []
	SubgraphDict1 = {}
	for key in SubGraphNodes:
		FD = frozenset(TollSumFromZero[key])
		if SubgraphDict1.get(FD) == None:
			SubgraphDict1[FD] = 1
		else:
			SubgraphDict1[FD] += 1
	for Comb in it.product(SubgraphDict1.keys(), repeat=2):
		if CombDict.get(Comb) == None:
			CombDict[Comb] = CombineSetPair(Comb)
		MultFactor = SubgraphDict1[Comb[0]] * SubgraphDict1[Comb[1]]
		if Comb[0] == Comb[1]:
			MultFactor -= SubgraphDict1[Comb[0]]
		if MultFactor > 0:
			CD = CombDict[Comb]
			for i1 in range(10):
				MasterOut[i1] += MultFactor * CD[i1]
for (I1, i1) in enumerate(MasterOut):
	print(i1)