#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;

	i = 1;
	while (S[i] != N) i++;
	i++;
	
	for (; i <= found; i++)
	{
		x = S[i];
		heapLen = 0;
		
		for (j = 1; j <= N; j++)
			Viz[j] = 1;
		
		if (Gr[x].size() > 0)
		{
			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;
}