#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
#define maxn 1024
#define inf 9999999999
#define PB push_back
#define MKP make_pair
#define ff first
#define ss second
#define PII pair<int, int>

int N, M, K;
int viz[maxn], ord[maxn], deg[maxn], cost[maxn][maxn], best[maxn][maxn];
vector<int> G[maxn], Gt[maxn];
multiset< pair<int, PII> > Heap;
multiset< pair<int, PII> >::iterator it;

void order() {
    int i, j, ok = 0;
    for(i=1; i<=N; i++) {
         if(!viz[i] && deg[i] == 0) {
              ok = 1;
              ord[0]++;
              ord[ ord[0] ] = i;
              viz[i] = 1;
              for(j=0; j<G[i].size(); j++) {
                   deg[ G[i][j] ]--;
              }
         }
    }
    if(ok) order();
}

int main() {
    FILE *f1=fopen("pitici.in", "r"), *f2=fopen("pitici.out", "w");
    int i, j, p, q;

    fscanf(f1, "%d %d %d\n", &N, &M, &K);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d %d\n", &p, &q, &j);
         G[p].PB( q );
         Gt[q].PB( p );
         cost[p][q] = cost[q][p] = j;
         deg[q]++;
    }

    order();

    for(i=1; i<=N; i++) {
         for(j=1; j<=K; j++) {
              best[i][j] = inf;
         }
    }
    best[1][1] = 0;

    for(i=2; i<=N; i++) {
         Heap.clear();
         int nod = ord[i];
         for(j=0; j<Gt[nod].size(); j++) {
              Heap.insert( MKP( best[ Gt[nod][j] ][1] + cost[nod][ Gt[nod][j] ], MKP(Gt[nod][j], 1) ) );
         }
         int nrdr = 0;
         while(nrdr < K && Heap.size()) {
              it = Heap.begin();
              nrdr++;
              best[nod][nrdr] = (*it).ff;
              Heap.erase(it);

              if(best[ (*it).ss.ff ][ (*it).ss.ss + 1 ] < inf) {
                   Heap.insert( MKP( best[ (*it).ss.ff ][ (*it).ss.ss + 1 ] + cost[nod][ (*it).ss.ff], MKP((*it).ss.ff, (*it).ss.ss + 1) ) );
              }
         }
    }

    for(i=1; i<=K; i++) {
         fprintf(f2, "%d ", best[N][i]);
    }

    fclose(f1); fclose(f2);
    return 0;
}