//huan
#include <bits/stdc++.h>
using namespace std;

const int N = 310;
int subid, T, n, m;
char sK[N];
typedef long long ll;
const ll P = 998244353;
__int128 eg[N][N], mx = 1;

namespace solve1{
    struct mat{
        __int128 a[N][N];
    } a;
    mat mul(mat x, mat y){
        mat z;
        for(int i = 0; i < N; ++ i){
            for(int j = 0; j < N; ++ j){
                z.a[i][j] = mx;
            }
        }
        for(int k = 1; k <= n; ++ k){
            for(int i = 1; i <= n; ++ i){
                for(int j = 1; j <= n; ++ j){
                    z.a[i][j] = min(z.a[i][j], x.a[i][k] + y.a[k][j]);
                    z.a[i][j] = min(z.a[i][j], mx);
                }
            }
        }
        return z;
    }
    mat qp(mat x, ll v){
        mat ans = x;
        -- v;
        while(v){
            if(v & 1){
                ans = mul(ans, x);
            }
            x = mul(x, x);
            v >>= 1;
        }
        return ans;
    }
    int main(){
        for(int i = 1; i <= n; ++ i){
            for(int j = 1; j <= n; ++ j){
                a.a[i][j] = eg[i][j];
                // printf("%d %d %lld\n", i, j, (ll)a.a[i][j]);
            }
        }
        ll k = 0;
        for(int i = 1; i <= strlen(sK + 1); ++ i){
            k = k * 10 + sK[i] - '0';
        }
        a = qp(a, k);
        for(int i = 1; i <= n; ++ i){
            if(a.a[1][i] == mx){
                printf("-1 ");
                continue;
            }
            ll v = a.a[1][i] % P;
            printf("%lld ", v);
        }
        puts("");
        return 0;
    }
}

int main(){
    for(int i = 1; i <= 37; ++ i){
        mx *= 10;
    }
    scanf("%d%d", &subid, &T);
    while(T--){
        for(int i = 0; i < N; ++ i){
            for(int j = 0; j < N; ++ j){
                eg[i][j] = mx;
            }
        }
        memset(sK, 0, sizeof(sK));
        scanf("%d%d", &n, &m);
        scanf("%s", sK + 1);
        for(int i = 1; i <= m; ++ i){
            int u, v;
            ll w;
            scanf("%d%d%lld", &u, &v, &w);
            __int128 ww = w;
            eg[u][v] = min(eg[u][v], ww);
        }
        if(subid == 1){
            solve1::main();
        }
    }
    return 0;
}