#include <bits/stdc++.h>

#define el '\n'
#define fi first
#define sec second
#define pb push_back
#define ll long long
#define pii pair<int,int>
#define sz(v) (int)(v).size()
#define all(v) (v).begin(),(v).end()
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
#define REP(i, a, b) for(int i = (a), _b = (b); i >= _b; i--)

using namespace std;

const long long LLNF = 0x3f3f3f3f3f3f3f3f;
const int MAX_N = 44444;

struct Huyen_Tram{
    ll len;
    int nho, type, u;
};

struct cmp{
    bool operator()(const Huyen_Tram &x, const Huyen_Tram &y){
        return x.len > y.len;
    }
};

vector<pii> g[MAX_N + 5];
ll dist[MAX_N + 5][5][200];
int n, m, k;

void Input(){
    cin >> n >> m >> k;
    FOR(i, 1, m){
        int u, v, w;
        cin >> u >> v >> w;
        g[u].pb({v, w});
        g[v].pb({u, w});
    }
}

inline ll power(ll x){
    ll res = 1;
    FOR(i, 1, k) res *= x;
    return res;
}

void dijk(){
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<Huyen_Tram, vector<Huyen_Tram>, cmp> pq;

    pq.push({0, 0, 0, 1});
    dist[1][0][0] = 0;

    while(sz(pq)){
        int u = pq.top().u;
        int type = pq.top().type;
        int nho = pq.top().nho;
        ll len = pq.top().len;
        pq.pop();

        if(len > dist[u][type][nho]) continue;

        for(pii x : g[u]){
            int v = x.fi, w = x.sec;

            int next_type = (type + 1) % k;
            int next_nho = (next_type == 0 ? 0 : nho + w);
            ll add = (next_type == 0 ? power(nho + w) : 0);

            if(dist[v][next_type][next_nho] > len + add){
                dist[v][next_type][next_nho] = len + add;
                pq.push({dist[v][next_type][next_nho], next_nho, next_type, v});
            }
        }
    }
}

void Solve(){
    dijk();
    FOR(i, 1, n){
        if(dist[i][0][0] != LLNF) cout << dist[i][0][0] << " ";
        else cout << -1 << " ";
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    Input();
    Solve();
}