题目描述

Bessie 得到一个无向图，包含 $N$ ($1\le N\le 2 \cdot 10^5$) 个顶点，编号为 $1\dots N$，以及 $M$ 条边 ($N - 1\le M\le 2 \cdot 10^5$)。每条边由两个整数 $u, v$ ($1\le u, v \le N$) 描述，表示连接节点 $u$ 和 $v$ 的无向边，以及一个范围在 a..z 之间的小写拉丁字母 $c$，作为该边的权值。保证给定的图是连通的。图中可能存在重边或自环。

定义 $f(a, b)$ 为从节点 $a$ 出发到达节点 $b$ 的所有路径中，边权拼接后字典序最小的字符串。路径可以多次经过同一条边（即允许经过环）。

对于每个 $i$ ($1\le i \le N$)，请帮助 Bessie 确定 $f(1, i)$ 的长度。如果长度有限，输出该长度；否则输出 $-1$。

输入格式

第一行包含 $T$ ($1\le T\le 10$)，表示独立测试用例的数量。 每个测试用例的格式如下：

第一行包含 $N$ 和 $M$。

接下来的 $M$ 行，每行包含两个整数和一个小写拉丁字母。

保证所有测试用例中 $N$ 的总和与 $M$ 的总和均不超过 $4\cdot 10^5$。

输出格式

对于每个测试用例，在一行中输出 $N$ 个以空格分隔的整数。

样例

输入 1

2
1 0
2 2
1 1 a
2 1 b

输出 1

0
0 -1

说明 1

对于第一个测试用例，节点 1 可以通过空路径到达，因此答案为 0。在第二个测试用例中，节点 2 没有字典序最小的路径，因为 FJ 可以在移动到节点 2 之前多次重复经过 'a' 自环，从而产生任意长度且字典序依然最小的字符串。因此，节点 2 的答案为 -1。

输入 2

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

输出 2

0 1 1 5 2 3 4
0 1 2 -1

说明 2

对于第一个测试用例，节点 1 的距离为 0。节点 2 和 3 与节点 1 相邻，距离为 1。对于节点 4、5、6 和 7，可以证明字典序最短路径不经过节点 2 和 4 之间的边。

对于第二个测试用例，节点 4 同样没有字典序最小的路径，因为字符串可以无限延长且保持字典序最小。因此，其答案为 -1。

子任务

• 测试点 3-4：每个字符均为 a。
• 测试点 5-8：每个字符均为 a 或 b。
• 测试点 9-14：$N,M\le 5000$。
• 测试点 15-22：无附加限制。