邪恶最短路

题目描述

给定一张有 $N$ 个顶点、$M$ 条边的有向图。顶点编号为 $1,2,\dots,N$。第 $i$ 条边从顶点 $A_i$ 指向顶点 $B_i$，边上写着一个 $1$ 到 $9$ 之间的数字 $C_i$。

沿着边的方向移动时，把经过的边上的数字按经过顺序拼接起来得到的整数，称为这次移动的得分。例如，依次经过数字 $3,1,4$ 的边，这次移动的得分就是 $314$。同一个顶点或同一条边可以被经过多次。

对每个 $v=2,3,\dots,N$，求从顶点 $1$ 出发到达顶点 $v$ 的所有移动中，得分的最小值对 $998244353$ 取模的结果。保证给定的有向图可以从顶点 $1$ 沿边到达其他所有顶点。

输入格式

第一行两个整数 $N, M$。

接下来 $M$ 行，第 $i$ 行三个整数 $A_i, B_i, C_i$，表示第 $i$ 条边。

输出格式

输出 $N-1$ 行。第 $(v-1)$ 行表示顶点 $v$ 的答案。

4 4
1 2 1
1 3 1
2 4 9
3 4 2

1
1
12

样例 1 解释

到顶点 $2$ 的最小得分为 $1$，到顶点 $3$ 的最小得分为 $1$。 到顶点 $4$ 可以走 $1\to2\to4$，得分为 $19$；也可以走 $1\to3\to4$，得分为 $12$。最小值为 $12$。

3 5
1 2 9
1 2 2
2 2 1
1 3 9
2 3 1

2
9

样例 2 解释

到顶点 $2$ 可以直接走数字为 $2$ 的边，得分为 $2$。 到顶点 $3$ 可以先走到顶点 $2$ 再走数字为 $1$ 的边，得分为 $21$；也可以直接走数字为 $9$ 的边，得分为 $9$。最小值为 $9$。

11 11
1 2 9
2 3 9
3 4 8
4 5 2
5 6 4
6 7 4
7 8 3
8 9 5
9 10 3
9 10 2
10 11 9

9
99
998
9982
99824
998244
9982443
99824435
998244352
998244352

样例 3 解释

从顶点 $1$ 到顶点 $11$ 的最小得分为 $9982443529$，对 $998244353$ 取模后为 $998244352$。 到顶点 $10$ 时，走数字为 $3$ 的边得到 $998244353$，走数字为 $2$ 的边得到 $998244352$，后者更小。

数据范围

对于所有测试数据，保证：

• $2\le N\le 2\times 10^5$；
• $N-1\le M\le 2\times 10^5$；
• $1\le A_i,B_i\le N$，$1\le C_i\le 9$；
• 可以从顶点 $1$ 沿边到达其他所有顶点。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。