#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 <std::pair <int, int>> reverse[maxn];

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

int dist[maxn][maxn];
int e[maxn][maxn];

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 <std::pair <int, int>, std::vector <std::pair <int, int>>, std::greater <std::pair <int, int>>> pq;

    dist[1][0] = 1;
    std::vector <int> parents;

    for (int it=1; it<V; it++){
        int node = nodes[it];

        int ind[maxn] = {};
        parents.clear();
        while (pq.empty() == false)
            pq.pop();
        for (int i=0; i<reverse[node].size(); i++){
            parents.push_back (reverse[node][i].first);
            //std::cout << reverse[node][i].first << '\n';
            pq.push ({dist[reverse[node][i].first][0] + reverse[node][i].second, i});
            ind[i] = 0;
        }

        for (int i=0; i<K and pq.empty() == false; i++){
            dist[node][i] = pq.top().first;
            int ii = pq.top().second;
            pq.pop();
            ind[ii] ++;
            if (dist[parents[ii]][ind[ii]] > 0){
                int new_dist = dist[parents[ii]][ind[ii]] + e[node][parents[ii]];
                pq.push ({new_dist, ii});
            }
        }
    }

    for (int i=0; i<K; i++)
        fout << dist[V][i] - 1 << ' ';
}


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});
        reverse[dest].push_back ({src, cost});
        e[src][dest] = cost;
        e[dest][src] = cost;
    }

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

    dijkstra (V, K);
    return 0;
}