BFS で解けます。公式解説の方法から BFS を設計したものとほぼ同じですが、ループ不変条件からスコアの順位が従うため明示的に計算しなくてもよいことを説明します。

簡単のため、スコアが相異なる場合を考えます。ループ不変条件は以下の通りです。

• BFS queue が空のときは、全ての頂点のスコアが求まっている。
• そうでないとき、queue 先頭の頂点のスコアを \(x\) と置き、以下の条件を全て満たす。
  • スコアが \([0, x)\) の範囲にある全ての頂点はスコアが求まっている。
  • スコアが \([x, 10x)\) の範囲にある全ての頂点はスコアが求まっている。また、頂点をスコアの昇順に並べた列は queue が表す列と一致する。
  • スコアが \([10x, \infty)\) の範囲にある全ての頂点は未探索である。

queue の先頭からスコア \(x\) の頂点 \(i\) を取り出すとき、スコアが \([10x, 10(x+1))\) の範囲にある頂点を過不足なく列挙し、queue の末尾にスコア順で追加できれば十分です。実際、以下のアルゴリズムはこれを満たします。

• 書かれている数字の昇順に、頂点 \(i\) から出ている辺を見る。
• 辺 \(i \xrightarrow{c} j\) について、頂点 \(j\) のスコアが確定しているならスキップする。
• そうでないならば、頂点 \(j\) のスコアを \(10x + c\) で確定し、queue の末尾に \(j\) を追加する。

以上より、辺を見る順番だけ気を付けて BFS をすると求まることが分かります。

さて、複数の頂点で同じスコアを取りうる場合を考えます。上のアルゴリズムをそのまま適用することはできませんが、頂点の代わりに「スコアが等しい頂点集合」を queue に入れ、頂点集合から出ている辺を一斉に見ることで正しく動作させることができます。

以上のアルゴリズムは時間計算量 \(O(N+M)\) です。

実装例 (Rust)

use std::collections::VecDeque;
use ac_library::ModInt998244353 as Mint;
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        N: usize, M: usize, ABC: [(Usize1, Usize1, usize); M]
    }
    
    let mut E = vec![vec![vec![]; 10]; N];
    for (a, b, c) in ABC { E[a][c].push(b); }
    
    let mut seen = vec![false; N]; seen[0] = true;
    let mut ans = vec![Mint::new(0); N];
    let mut deq = VecDeque::new(); deq.push_back(vec![0]);
    
    while let Some(set) = deq.pop_front() {
        // 数字の昇順に見る
        for c in 1..10 {
            let mut nx_set = vec![];

            // 頂点集合 set に含まれる頂点 i について
            // c が書かれた辺を一斉に見る
            for &i in &set {
                for &j in &E[i][c] {
                    if seen[j] { continue; }
                    seen[j] = true;
                    ans[j] = ans[i]*10 + c;
                    nx_set.push(j);
                }
            }

            if !nx_set.is_empty() {
                deq.push_back(nx_set);
            }
        }
    }
    
    for i in 1..N { println!("{}", ans[i]); }
}