#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, m, k, i, j, in[1020];
vector<pair<int, int> > graph[1020];
vector<int> sol[1020];
queue<int> q;
struct comp{
    bool operator()(int x, int y){
        return x<=y;
    }
} c;
int main()
{
    freopen("pitici.in", "r", stdin);
    freopen("pitici.out", "w", stdout);
    scanf("%d%d%d", &n, &m, &k);
    for(i=1; i<=m; ++i){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        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();
        sort(sol[node].begin(), sol[node].end(), c);
        if(sol[node].size()>k) sol[node].erase(sol[node].begin()+k, sol[node].end());
        for(auto i:graph[node]){
            for(auto j:sol[node]) sol[i.first].push_back(j+i.second);
            --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;
}