#include <bits/stdc++.h>
#define maxn 1020

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

std::vector <std::pair <int, int>> edge[maxn];

std::vector <int> ans;
std::vector <int> nodes;

bool visited[maxn];
std::stack <int> st;
void topologicalSort (int node){
    visited[node] = true;
    for (int i=0; i<edge[node].size(); i++){
        int next = edge[node][i].first;
        if (visited[next] == false)
            topologicalSort(next);
    }
    st.push (node);
}


void dijkstra (int V, int K){
    std::priority_queue <int> pq[V+1];
    pq[1].push (0);

    for (int it=0; it<V-1; it++){
        int node = nodes[it];
        while (pq[node].empty() == false){
            int cost = pq[node].top();
            pq[node].pop();
            for (int i=0; i<edge[node].size(); i++){
                int next = edge[node][i].first;
                int next_cost = cost + edge[node][i].second;
                if (pq[next].size() == K){
                    if (pq[next].top() > next_cost){
                        pq[next].pop();
                        pq[next].push (next_cost);
                    }
                }
                else
                    pq[next].push (next_cost);
            }
        }
    }

    std::vector <int> ans;

    while (pq[V].empty() == false){
        ans.push_back (pq[V].top());
        pq[V].pop();
    }
    for (int i=ans.size()-1; i>=0; i--)
        fout << ans[i] << ' ';
}


int main()
{
    int V, E, K, src, dest, cost, i;
    fin >> V >> E >> K;
    for (i=0; i<E; i++){
        fin >> src >> dest >> cost;
        edge[src].push_back ({dest, cost});
    }

    topologicalSort(1);
    while (st.empty() == false){
        nodes.push_back (st.top());
        st.pop();
    }

    dijkstra (V, K);
    return 0;
}