[CSES] Shortest Routes II

void solve() {
    ll n, m, q;
    cin >> n >> m >> q;

    vvll v(n, vll(n, inf));
    rep(i, m) {
        ll x, y, w;
        cin >> x >> y >> w;
        --x, --y;
        v[x][y] = min(v[x][y], w);
        v[y][x] = v[x][y];
    }
    rep(i, n) v[i][i] = 0;
    debug(v);

    vvll dp = v;
    rep(i, n) {
        rep(a, n) {
            rep(b, n) {
                if (dp[a][i] < inf && dp[i][b] < inf) {
                    dp[a][b] = min(dp[a][b], dp[a][i] + dp[i][b]);
                }
            }
        }
    }
    debug(dp);

    while (q--) {
        ll a, b;
        cin >> a >> b;
        --a, --b;

        if (dp[a][b] == inf) cout << -1 << "\n";
        else cout << dp[a][b] << "\n";
    }
}