#include<stdio.h>
#include<vector>
#include<set>
using namespace std;
#define nmax 1025
struct element{long n, c;};
long n, m, i, a, b, c, inc, sf, el, k;
long gr[nmax], co[nmax];
vector <element> ma[nmax];
vector <element> ::iterator it;
multiset <long> v[nmax];
multiset <long> ::iterator itv, ult;
element mch, x;

void citire()
{
    scanf("%ld %ld %ld",&n,&m,&k);
    for (i=1;i<=m;i++)
    {
        scanf("%ld %ld %ld",&a,&b,&c);
        mch.n=b; mch.c=c; ma[a].push_back(mch);
        gr[b]++;
    }
}

void rezolvare()
{
    v[1].insert(0);
    co[++sf]=1; inc=1;
    while (inc<=sf)
    {
        el=co[inc]; inc++;
        for (it=ma[el].begin();it!=ma[el].end();it++)
        {
            x=*it;
            gr[x.n]--;
            if (!gr[x.n])
                co[++sf]=x.n;
            for (itv=v[el].begin();itv!=v[el].end();itv++)
            {
                v[x.n].insert(*itv+x.c);
                if (v[x.n].size()==k+1)
                {
                    ult=v[x.n].end();    ult--;
                    v[x.n].erase(ult);
                }
            }
        }
    }
}

void afisare()
{
    for (itv=v[n].begin();itv!=v[n].end();itv++)
        printf("%ld ",*itv);
}

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