#include <bits/stdc++.h>
using namespace std;
const int N = 1020;
ifstream fin("pitici.in");
ofstream fout("pitici.out");
#define cin fin
#define cout fout
int n, m, k;
vector<pair<int, int>> liste[N], listet[N];
vector<long long> vl[N];
void top_sort(){
    vector<int> d(N);
    for(int i = 1; i <= n; i++){
        for(auto j : liste[i]){
            if(d[j.first]++);
        }
    }
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(!d[i]){
            vl[i].push_back(0);
            q.push(i);
        }
    }
    while(q.size()){
        int nod = q.front();
        q.pop();
        for(auto i : listet[nod]){
           
            vector<long long> p;
            int p1 = 0, p2 = 0;
            while(p1 < vl[nod].size() && p2 < vl[i.first].size() && p.size() < k){
                if(vl[nod][p1] <= vl[i.first][p2] + i.second){
                    p.push_back(vl[nod][p1]);
                    p1++;
                }else{
                    p.push_back(vl[i.first][p2] + i.second);
                    p2++;
                }
            }
            while(p.size() < k && p1 < vl[nod].size()){
                p.push_back(vl[nod][p1++]);
            }
            while(p.size() < k && p2 < vl[i.first].size()){
                p.push_back(vl[i.first][p2++] + i.second);
            }
            swap(vl[nod], p);
        }
        // sort(vl[nod].begin(), vl[nod].end());
        // while(vl[nod].size() > k){
        //     vl[nod].pop_back();
        // }
        for(auto i : liste[nod]){
            if(--d[i.first] == 0){
                q.push(i.first);
            }
        }
    }

}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++){
        int u, v, c;
        cin >> u >> v >> c;

        liste[u].push_back({v, c});
        listet[v].push_back({u, c});
    }
    top_sort();
    assert(vl[n].size() == k);
    for(auto i : vl[n]){
        cout << i << " ";
    }
}