Bessie is given an undirected graph with N (1≤N≤2⋅105) vertices labeled 1…N and M edges (N−1≤M≤2⋅105). Each edge is described by two integers u,v(1≤u,v≤N) describing an undirected edge between nodes u and v and a lowercase Latin letter c in the range a..z that is the value on the edge. The graph given is guaranteed to be connected. There may be multiple edges or self-loops.
Define f(a,b) as the lexicographically smallest concatenation of edge values over all paths starting from node a and ending at node b. A path may contain the same edge more than once (i.e., cycles are allowed).
For each i (1≤i≤N), help Bessie determine the length of f (1,i). Output this length if it is finite, otherwise output −1.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤10), the number of independent tests. Each test is specified in the following format:
The first line contains N and M.
The next M lines each contain two integers followed by a lowercase Latin character.
It is guaranteed that neither the sum of N nor the sum of M over all tests exceeds 4⋅105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test, output N space-separated integers on a new line.
SAMPLE INPUT:
2
1 0
2 2
1 1 a
2 1 b
SAMPLE OUTPUT:
0
0 -1
For the first test case, node 1 can be reached with an empty path, so the answer is 0. In the second test case, node 2 cannot have a lexicographically smallest path, since FJ can repeat the 'a' self-loop any number of times before moving to node 2, producing arbitrarily long strings that are still lexicographically minimal. Therefore, the answer for node 2 is -1.
SAMPLE INPUT:
2
7 7
1 2 a
1 3 a
2 4 b
3 5 a
5 6 a
6 7 a
7 4 a
4 3
1 2 z
2 3 x
3 4 y
SAMPLE OUTPUT:
0 1 1 5 2 3 4
0 1 2 -1
For the first test case, node 1 has distance 0. Nodes 2 and 3 are adjacent with node 1, and they have distance 1. For nodes 4, 5, 6, and 7, it can be proven that the lexicographically shortest path does not pass through the edge between node 2 and 4.
For the second test case, node 4 again has no lexicographically smallest path, since the string can be extended indefinitely while remaining lexicographically minimal. Thus, its answer is -1.
SCORING:
Inputs 3-4: Every character is a.
Inputs 5-8: Every character is a or b.
Inputs 9-14: N,M≤5000
Inputs 15-22: No additional constraints.
Problem credits: Daniel Zhu and Yash Belani