#include <fstream>
#include <vector>
#define MAX 1020

using namespace std;

struct Nodes{
    int x, c;
} aux;
vector<vector<Nodes> > a;
vector<Nodes> heap;
vector<int> q;

int d[MAX][MAX], pus[MAX], T[MAX];
int n, m, k;

void DF(int nod)
{
    int i;
    for (i = 0; i < a[nod].size(); i++)
        DF(nod);
    q.push_back(nod);
}

int MIN(int i, int j){
	int ca = (i <= m) ? (d[heap[i].x][T[heap[i].x]] + heap[i].c) : 1000000000;
	int cb = (j <= m) ? (d[heap[j].x][T[heap[j].x]] + heap[j].c) : 1000000000;
	if (ca < cb) return i;
	return j;
}

void Swap(int x,int y){
	aux = heap[x];
	heap[x] = heap[y];
	heap[y] = aux;
}

void HeapUp(int i){
	if (i != 1){
		if (MIN(i,i/2) == i) Swap(i,i/2),  HeapUp(i/2);
	}
}

void HeapDw(int i){
	int k = MIN(i*2, i*2+1);
	if (MIN(k,i) != i) Swap(i,k),HeapDw(k);
}

int main()
{
    int i, x1, x2, cost;
    
    ifstream fin("pitici.in");    
    fin >> n >> m >> k;
    a.resize(n+1);
    for (i = 1; i <= m; i++)
    {
        fin >> x1 >> x2 >> cost;
        aux.x = x2;
        aux.c = cost;
        a[x1].push_back(aux);    
    }
    fin.close();
    
    DF(1);
    
    memset(pus, 0, sizeof(pus));
    memset(d, 1, sizeof(d));
    pus[1] = 1;
    d[1][1] = 0;
    
    int nod, j;
    
    for (i = 1; i < n; i++)
    {
        for (j = 1; j <= n; j++) { T[j] = 1; }    
        
        nod = q[i]; m = 0;
        
        for (i = 0; i < a[nod].size(); i++)
        {
            m++;
            heap[m].x = a[nod][i].x;
            heap[m].c = a[nod][i].c;
            HeapUp(m);        
        } 
        
        for (; m && pus[nod] <= k;)       
        {
            d[nod][++pus[nod]] = d[heap[1].x][T[heap[1].x]++] + heap[1].c;
            if (T[heap[1].x] <= pus[heap[1].x]) HeapDw(1);
            else 
            {
                Swap(1, m);
                m--;
                HeapDw(1);            
            }    
        }    
    }
    
    ofstream fout("pitici.out");
    for (i = 1; i <= k; i++)
        fout << d[n][i] << " ";
    fout.close();
    
    return 0;
}