// Pitici, Infoarena/Lot 2006
// http://infoarena.ro/problema/pitici

#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <cstring>
#include <set>
#include <list>
#include <queue>
using namespace std;

const int NMAX = 1024;

int n, m, k;
multiset<int> Costs[NMAX];
list<pair<int, int> > Neighb[NMAX];
bool Used[NMAX];
list<int> Done;


void depthFirst(int n) {
	int next;
	list<pair<int, int> >::iterator it;
	for (it = Neighb[n].begin(); it != Neighb[n].end(); ++ it) {
		next = it->first;
		if (Used[next] == false) {
			Used[next] = true;
			depthFirst(next);
		}
	}
	Done.push_back(n);
}

void costUpdate(int n) {
	list<pair<int, int> >::iterator it;
	multiset<int>::iterator msi, aux;
	int next, cost, i;
	for (it = Neighb[n].begin(); it != Neighb[n].end(); ++ it) {
			next = it->first;
			cost = it->second;
		
			for (msi = Costs[n].begin(), i = 0; msi != Costs[n].end() && i < k; ++ msi, ++ i) {
				Costs[next].insert(*msi + cost);
				if (Costs[next].size() > k) {
					aux = Costs[next].end();
					-- aux;
					Costs[next].erase(aux);
				}
			}
	}
}

int main() {

	freopen("pitici.in", "r", stdin);
	freopen("pitici.out", "w", stdout);

	scanf("%d %d %d", &n, &m, &k);
	int i, v1, v2, c;
	for (i = 0; i < m; ++ i) {
		scanf("%d %d %d", &v1, &v2, &c);
		Neighb[v1].push_back(make_pair(v2, c));
	}

	memset(Used, 0, false);
	Used[1] = true;
	depthFirst(1);

	Costs[1].insert(0);
	list<int>::reverse_iterator li;
	for (li = Done.rbegin(); li != Done.rend(); ++ li)
		costUpdate(*li);

	multiset<int>::iterator msi;
	for (msi = Costs[n].begin(); msi != Costs[n].end(); ++ msi)
		printf("%d ", *msi);

	return 0;
}