#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 300005
#define sti string
#define int long long

using namespace std;

int val[maxn],Rank[maxn],test;
vector<pair<int,int>> adj[maxn];
bool vis[maxn];
const int mod = 998244353;

struct node {
  int idx,w,v,u;
};

signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>test;
    while(test--){
        int n,m,k;
        cin>>n>>m>>k;
        for(int i=1;i<=n;i++) {
            adj[i].clear();
            vis[i] = 0;
            Rank[i] = 0;
            val[i] = 0;
        }
        for(int i=1;i<=m;i++){
            int u,v,w;
            cin>>u>>v>>w;
            adj[u].push_back({v,w});
            adj[v].push_back({u,w});
        }
        vector<int> cur;
        cur.push_back(1);
        vis[1] = 1;
        for(int u : cur){
            for(auto [v,w] : adj[u]){
                if(w == 0 && !vis[v]){
                    vis[v] = 1;
                    cur.push_back(v);
                }
            }
        }
        while(!cur.empty()){
            vector<node> vec;
            for(int u : cur){
                for(auto [v,w] : adj[u]){
                    if(!vis[v]){
                        vec.push_back({Rank[u],w,v,u});
                    }
                }
            }
            sort(vec.begin(), vec.end(), [](const node& a, const node& b) {
                if (a.idx != b.idx) return a.idx < b.idx;
                return a.w < b.w;
            });
            vector<int> nxt;
            int curidx = -1;
            int lastidx = -1,lastW = -1;
            for(auto [idx,w,v,u] : vec){
                if(vis[v]) continue;
                if(idx != lastidx || w != lastW){
                    curidx++;
                    lastidx = idx;
                    lastW = w;
                }
                vis[v] = 1;
                Rank[v] = curidx;
                val[v] = ((val[u] * k % mod) + w)%mod;
                nxt.push_back(v);
            }
            cur = nxt;
        }
        for(int i=1;i<=n;i++) {
            if(!vis[i]) cout<<-1<<' ';
            else cout<<val[i]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}