#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<vector>
using namespace std;

const char IN[] = {"pitici.in"};
const char OUT[] = {"pitici.out"};
const int INF = 1000000005;
const double PI  = 3.14159265;
const int NMAX = 1050;
const int KMAX = 1050;

#define II inline
#define LL long long
#define PII pair<int, int>
#define PDD pair<double, double>
#define fs first
#define ss second
#define mp make_pair
#define pb push_back
#define FOR(i, a, b)     for(int i = a ; i <= b ; i++)
#define IFOR(i, a, b)     for(int i = a ; i >= b ; i--)
#define FORIT(it, V)     for(vector<int> :: iterator it = V.begin() ; it != V.end() ; it++)
#define all(a) a, a +

int N, M, K;
vector<int> Graf[NMAX], Inv[NMAX];
int ord[NMAX];
int drum[NMAX][KMAX];
int cost[NMAX][NMAX];
int nod;

struct comp
{
    bool operator()(const PII a, const PII &b)const
    {
        return drum[a.fs][a.ss] + cost[a.fs][nod] > drum[b.fs][b.ss] + cost[b.fs][nod];
    }
};

priority_queue<int, vector<PII>, comp> PQ;

void citi()
{
    scanf("%d%d%d", &N, &M, &K);
    FOR(i, 1, M)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        Graf[x].pb(y);
        cost[x][y] = c;
        Inv[y].pb(x);
    }
    
}

void sort_top()
{
    queue<int> Q;
    int in[NMAX];
    FOR(i, 1, N)
    {
        if(!Inv[i].size())    Q.push(i);
        in[i] = Inv[i].size();
    }
    
    while(!Q.empty())
    {
        int x = Q.front();
        Q.pop();
        ord[++ord[0]] = x;
        FORIT(it, Graf[x])
        {
            in[*it]--;
            if(!in[*it])
                Q.push(*it);
        }
    }
}

void obt_sol()
{
    FOR(i, 1, N)    FOR(j, 1, K)    drum[i][j] = INF;
    drum[1][1] = 0;
    
    FOR(i, 2 , N)
    {
		nod = ord[i];
        FORIT(it, Inv[nod])
            PQ.push(mp(*it, 1));
        for(int j = 1 ; j <= K && PQ.size(); j++)
        {
            PII x = PQ.top();
            PQ.pop();
            drum[nod][j] = drum[x.fs][x.ss] + cost[x.fs][nod];
            if(drum[x.fs][x.ss + 1] != INF)
                PQ.push(mp(x.fs, x.ss + 1));
        }
        while(!PQ.empty())    PQ.pop();
    }
}

void scrie()
{
    FOR(j, 1, K)
        printf("%d ", drum[N][j]);
    printf("\n");
}

int main()
{
    freopen(IN, "r", stdin);
    freopen(OUT, "w", stdout);
    citi();
    sort_top();
    obt_sol();
    scrie();
    return 0;
}