#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

///PRACTICE
using namespace std;

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

const int NMAX=1024;

vector<int>v1[NMAX];
vector<int>v2[NMAX];
vector<int>dp[NMAX];
vector<int>topos;

bool viz[NMAX];
int c[NMAX][NMAX];

struct elem{
    int node;
    int cost;
    int poz;
    bool operator<(const elem &x) const{
        return cost>x.cost;
    }
};

priority_queue<elem>heap;

void dfs(int p)
{
    viz[p]=1;
    for(auto i:v1[p])
    {
        if(!viz[i])
            dfs(i);
    }
    topos.push_back(p);
}

void build_heap()
{
    dfs(1);
    dp[1].push_back(0);
    reverse(topos.begin(),topos.end());
}

int main()
{
    int n,m,k,i,j,x,y,z;
    fin>>n>>m>>k;
    while(m--)
    {
        fin>>x>>y>>z;
        v1[x].push_back(y);
        v2[y].push_back(x);
        c[x][y]=z;
    }
    build_heap();
    for(auto i:topos)
    {
        while(!heap.empty())
            heap.pop();
        for(auto j:v2[i])
            heap.push({j,dp[j][0]+c[j][i],0});
        for(int l=1;l<=k;l++)
        {
            if(heap.empty())
                break;
            elem p=heap.top();
            dp[i].push_back(p.cost);
            heap.pop();
            if(p.poz+1<dp[p.node].size())
                heap.push({p.node,dp[p.node][p.poz+1]+c[p.node][i],p.poz+1});
        }
    }
    for(auto i:dp[n])
        fout<<i<<" ";
    return 0;
}