#include <bits/stdc++.h>
#define Nmax 1020
#define INF Nmax * Nmax
#define pi pair<int, int>
#define pb push_back
using namespace std;

ifstream f("pitici.in");
ofstream g("pitici.out");

int N, M, K, len;
vector<pi> G[Nmax], GT[Nmax];
vector<int> road[Nmax];
int aux[INF], a[Nmax];
bool vis[Nmax];

struct Node{
   int pos, lev;
};
Node v[Nmax];
bool cmp(Node a, Node b) {
   return a.lev < b.lev;
}

void DFS(int node, int father) {
    vis[node] = 1;
    v[node].lev = v[father].lev + 1;
    for (auto it: G[node])
        if (!vis[it.first]) DFS(it.first, node);
}
void compute(int x) {
    len = 0;
    for (auto it: GT[x])
    for (auto it2: road[it.first])
       aux[++len] = it2 + it.second;
    sort(aux + 1, aux + len + 1);
}
int main()
{
    f >> N >> M >> K;
    for (int i = 1; i <= M; ++i) {
        int x, y, c;
        f >> x >> y >> c;
        G[x].pb({y, c});
        GT[y].pb({x, c});
    }
    for (int i = 1; i <= N; ++i)
        v[i].pos = i;
    DFS(1, 0);
    sort(v + 1, v + N + 1, cmp);

    for (int i = 1; i <= N; ++i)
        a[i] = v[i].pos;

    road[1].pb(0);
    for (int i = 2; i <= N; ++i) {
        compute(a[i]);
        for (int j = 1; j <= min(len, K); ++j)
            road[a[i]].pb(aux[j]);
    }

    for (auto it: road[N])
        g << it << " ";
    return 0;
}