#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, k, i, j, in[1020], p;
vector<pair<int, int> > graph[1020];
vector<int> sol[1020];
queue<int> q;
struct comp{
    bool operator()(int x, int y){
        return x<=y;
    }
} co;
char c[30];
int read();
int main()
{
    freopen("pitici.in", "r", stdin);
    freopen("pitici.out", "w", stdout);
    fgets(c, 30, stdin); p=-1;
    n=read(); m=read(); k=read();
    for(i=1; i<=m; ++i){
        int x, y, z;
        fgets(c, 30, stdin); p=-1;
        x=read(); y=read(); z=read();
        graph[x].push_back({y, z});
        ++in[y];
    }
    sol[1].push_back(0);
    for(q.push(1); !q.empty(); q.pop()){
        int node=q.front();
        for(auto i:graph[node]){
            for(auto j:sol[node]) sol[i.first].push_back(j+i.second);
            sort(sol[i.first].begin(), sol[i.first].end(), co);
            if(sol[i.first].size()>k) sol[i.first].erase(sol[i.first].begin()+k, sol[i.first].end());
            --in[i.first];
            if(in[i.first]==0) q.push(i.first);
        }
        if(node!=n)sol[node].clear();
    }
    for(auto i:sol[n]) printf("%d ", i);
    return 0;
}
int read(){
    ++p; int nr=0;
    while(c[p]!='\n' && c[p]!=' ') {nr=nr*10+(c[p]-'0'); ++p;}
    return nr;
}