#include <fstream>
#include <vector>
#include <set>

#define NMAX 1024
#define KMAX 1024
#define INFI 2000000
#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

struct nod {int next, cost; };

set<pair<int, int> > H;
vector<nod> Gr[NMAX];

pair<int,int> heap[NMAX];

int A[NMAX][NMAX];

int N, M, K, S[NMAX], found, Viz[NMAX], best[NMAX][KMAX], heapLen;

int sortCond(pair<int, int> a, pair<int, int> b)
{
	if (a.first < b.first) return 0;
	else return 1;
}

void readAll(void)
{
	ifstream fin("pitici.in");
	
	fin >>N >>M >>K;
	
	int i, x;
	nod a;
	
	for (i = 1; i <= M; i++)
	{
		fin >>x >>a.next >>a.cost;
		Gr[x].pb(a);
	}
	
	fin.close();
}

void DFS(int x)
{
	for (int i = 0; i < Gr[x].size(); i++)
		if (Viz[Gr[x][i].next] == 0)
		{
			Viz[Gr[x][i].next] = 1;
			DFS(Gr[x][i].next);
		}
	S[++found] = x;
}

void Solve(void)
{
	DFS(1);
	
	int i, x, j, nx, cc, indnx;
	
	for (j = 1; j <= N; j++)
		for (i = 1; i <= K; i++)
			best[j][i] = INFI;
		
	best[N][1] = 0;

	for (; i <= found; i++)
	{
		x = S[i];
		heapLen = 0;
		
		for (j = 1; j <= N; j++)
			Viz[j] = 1;
		
		for (j = 0; j < Gr[x].size(); j++)
		{	
			heap[heapLen++] = mp( best[ Gr[x][j].next ][ Viz[ Gr[x][j].next  ]++ ] + Gr[x][j].cost , j);
		}
		make_heap(heap, heap + heapLen, sortCond);
		
		while (Viz[x] <= K)
		{
			best[x][Viz[x]++] = heap[0].ff;
			indnx = heap[0].ss;
			nx = Gr[x][heap[0].ss].next;
			cc = Gr[x][heap[0].ss].cost;
			pop_heap(heap, heap + heapLen, sortCond);
			heapLen--;
			
			if (Viz[nx] <= K)
			{
				heap[heapLen++] = mp( best[ nx ][ Viz[nx]++ ] + cc , indnx );
				push_heap(heap, heap + heapLen, sortCond);
			}
		}
	}
}

void writeResult(void)
{
	ofstream fout("pitici.out");
	
	for(int i = 1; i <= K; i++)
		fout <<best[1][i] <<' ';
	
	fout.close();
}

int main()
{
	readAll();
	
	Solve();
	
	writeResult();
	
	return 0;
}