直接スコアの最小値を管理することを意図した解法です。

頂点 \(p\) まで移動した際の最小値を \(X_p\) とします。

頂点 \(p\) から出る辺 ごとに次の頂点 \(nex\) に移動したスコアが現状の \(X_{nex}\) 未満ならば更新するという方法を考えます。

このとき \(1\) 辺移動するごとにスコアが \(10\) 倍以上になるため移動回数最小の経路で達成しうる値のみを考えればよいです。

よって BFS を行いながらスコアを更新していくことを考えます。

このときスコアをそのままコピーして計算すると \(O(N^2)\) になってしまうため TLE となります。

ここで更新に必要な処理はスコアの大小比較です。

数字の大小比較は桁数比較をし、一致するなら辞書順における大小関係を求められればよいです。

スコアを永続セグメント木上の列として管理することを考えます。

このとき Rolling Hash の値を持つと辞書順の比較が prefix が一致する上限に関しての二分探索を行うことで \(O(\log{N})\) で可能になります。

さらに各頂点でのスコアを \(998244353\) で割った値も別途管理することで \(O(N+M\log{N})\) で解くことができます。