#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define Nmax 1024
#define INF 0x3f3f3f3f
#define mp make_pair
#define pb push_back
#define sz size()
#define x first
#define y second

int n, m, k, ct, hs;
int ind[Nmax], v[Nmax], d[Nmax][Nmax], list[Nmax], add[Nmax], pos[Nmax], p[Nmax], h[Nmax];
vector< pair<int, int> > lv[Nmax];

void citire()
{
    int i, a, b, c;
    
    scanf("%d %d %d\n", &n, &m, &k);
    for (i = 1; i <= m; ++i)
    {
        scanf("%d %d %d\n", &a, &b, &c);
        lv[a].pb( mp(b, c) );
    }
}

int df(int nod)
{
    int ret = 0, i, lim = lv[nod].sz;
    
    v[nod] = 1;
    
    if (nod == n)
    {
        list[++ct] = nod;
        v[nod] = 2;
        return 1;
    }
    
    for (i = 0; i < lim; ++i)
        if (!v[lv[nod][i].x])
            if (df(lv[nod][i].x))
                ret = 1;
            else;
        else if (v[lv[nod][i].x] == 2)
            ret = 1;
    
    if (ret)
    {
        list[++ct] = nod;
        v[nod] = 2;
        return 1;
    }
    
    return 0;    
}

int cmp(int a, int b)
{
    int v1 = d[ pos[h[a]] ][ ind[pos[h[a]]] ] + add[ pos[h[a]] ];
    int v2 = d[ pos[h[b]] ][ ind[pos[h[b]]] ] + add[ pos[h[b]] ];
    
    return v1 < v2;
}

void combheap(int i)
{
    int tata, fiu;
    
    tata = i;
    fiu = tata * 2;
    
    while (fiu <= hs)
    {
        if (fiu < hs && cmp(fiu + 1, fiu))
            ++fiu;
        
        if (cmp(fiu, tata))
            swap(h[fiu], h[tata]);
        else
            break;
        
        tata = fiu;
        fiu = tata * 2;
    }
}

void solve()
{
    int i, j, lim, nod;
    
    df(1);
    reverse(list+1, list+ct+1);
    memset(v, 0, sizeof(v));
    
    for (i = 1; i <= ct; ++i)
        v[list[i]] = 1;
    /*
    for (i = 1; i <= ct; ++i)
        printf("%d ", list[i]);
    printf("\n");
    */
    for (i = 2; i <= k; ++i)
        d[ct][i] = INF;
    pos[n] = ct;
    
    for (i = ct - 1; i >= 1; --i)
    {
        nod = list[i];
        hs = 0;
        lim = lv[list[i]].sz;
        
        for (j = 0; j < lim; ++j)
            if (v[lv[nod][j].x])
            {
                ind[pos[lv[nod][j].x]] = 1;
                add[pos[lv[nod][j].x]] = lv[nod][j].y;
                h[++hs] = lv[nod][j].x;
            }
        
        for (j = hs / 2; j > 0; --j)
            combheap(j);
        
        for (j = 1; j <= k; ++j)
        {
            d[i][j] = d[ pos[h[1]] ][ ind[pos[h[1]]] ] + add[ pos[h[1]] ];
            ++ind[ pos[h[1]] ];
            combheap(1);
        }
        
        /*
        for (j = 1; j <= k; ++j)
            printf("%d ", d[i][j]);
        printf("\n");
        */
        pos[nod] = i;
    }
    
    for (i = 1; i <= k; ++i)
        printf("%d ", d[1][i]);
    printf("\n");
}

int main()
{
    freopen("pitici.in", "r", stdin);
    freopen("pitici.out", "w", stdout);
    citire();
    solve();
    return 0;
}