はじめに naive な dijkstra を提案し、それを高速化しましょう。

まず、各頂点について「頂点 \(1\) から、その頂点に到達するスコアの最小値」を管理する dijkstra が正当なことを確認しましょう。確認するべきは以下の二点です。

• 優先度付きキューに入るスコア（コスト）が広義単調増加になる

  任意の \(s ~ (\ge 0)\) と \(c ~ (1 \le c \le 9)\) について、 \(s \le 10s + c\) ですから、辺を通ると、スコアは増加します。よって、キューに入るスコアは単調増加になります。（これは、 dijkstra における負の辺が存在しないことに対応します）

• スコアの最小値だけを管理すればよい

  つまり、ある頂点における「二番目以降のスコア」を経由することが他の頂点において最適になることがないという主張です。任意の \(s \lt t\) と \(c ~ (1 \le c \le 9)\) について、 \(10s + c \lt 10t + c\) なので、 \(t\) を使用するような経路が最適解になることはありません。

ということで、これが正当であることはわかります。しかし、「スコアの文字数」は \(\Theta(N)\) となりうるため、これを直接管理しようとすると、 \(\Theta(N^2)\) となります。

上のアルゴリズムを高速化しましょう。

確定したスコアに小さい順に「順位」を付けることにします。すると、確定済みの頂点間では、スコアの代わりに順位で大小を比較できます。（同じスコアには同じ順位を付け、始点の順位は \(0\) とします）

スコア \(s,t\) の頂点から、それぞれ数字 \(c,d\) の辺を通る候補を「順位」を用いて比較しましょう。

\(s<t\) と \(1\le c,d\le9\) について

\[10s+c\le10s+9<10t+1\le10t+d\]

となります。一方、\(s=t\) なら、\(c,d\) の大小だけで決まります。したがって、移動後のスコアの大小は、次の組の辞書順と一致します。

\[\text{(移動元のスコアの順位},\ \text{辺の数字})\]

ということで、優先度付きキューに入れるスコアを、この組に置き換えればよいです。これは \(O(1)\) で管理・更新が出来ます。また、スコアを \(998244353\) で割ったあまりについては、これと同時に管理をすればよいです。（実装例を参照してください）

計算量は \(O(N + M \log M)\) となります。

実装例 (PyPy)

from heapq import heappush, heappop

mod = 998244353

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v, c = map(int, input().split())
    g[u - 1].append((v - 1, c))

ans = [-1] * n
ans[0] = 0

q = []
for v, c in g[0]:
    heappush(q, (0, c, v, c))

rank = 0
last = None

while q:
    r, c, v, x = heappop(q)
    if ans[v] != -1:
        continue

    if last != (r, c):
        rank += 1
        last = (r, c)

    ans[v] = x
    for u, d in g[v]:
        if ans[u] == -1:
            heappush(q, (rank, d, u, (10 * x + d) % mod))

print(*ans[1:], sep="\n")