#include <fstream>
#include <vector>
#include <queue>
#include <cstring>

#define nmax 1000
#define kmax 1000

const int INF = (1<<20);

using namespace std;
ifstream fin("pitici.in");
ofstream fout("pitici.out");

vector <int> stk;

struct hmch
{
    int nod;
    int c;
    int nrd;
};

struct cmp
{

    bool operator()(hmch a,hmch b)const
    {
        return a.c>b.c;
    }
};



vector <pair<int,int>> v[nmax + 5];

int mc[nmax + 5][nmax + 5];

int d[nmax + 4][kmax + 4];

bool viz[nmax + 4];

int n,m,k;

void dfs(int nod)
{
    viz[nod]=true;
    for(auto& i : v[nod])
        if(!viz[i.second])
            dfs(i.second);
    stk.push_back(nod);
}

int main()
{
    fin>>n>>m>>k;
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        fin>>x>>y>>c;
        mc[x][y]=c;
        v[x].push_back({c,y});
    }
    dfs(1);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=k; j++)
            d[i][j]=INF;
    d[n][1]=0;
    memset(viz,0,sizeof(viz));
    for(auto& nod : stk)
    {
        //fout<<nod<<' ';
        priority_queue<hmch,vector<hmch>,cmp> q;

        if(v[nod].empty())
            continue;

        for(auto& i : v[nod])
        {
            int vec = i.second;
            int cost = i.first;
            q.push({vec,d[vec][1] + cost,1});
        }
        for(int i=1;i<=k;i++)
        {
            if(q.empty())
                break;
            hmch x = q.top();
            q.pop();
            int vec = x.nod;
            int cost = x.c;
            int nrd = x.nrd;
            d[nod][i] =cost;
            q.push({vec,d[vec][nrd+1]+mc[nod][vec],nrd+1});

        }
    }

    for(int i=1;i<=k;i++)
        fout<<d[1][i]<<' ';
}