/*
TASK: cowjog
LANG: C++
ID: mystupidn1
*/

#include <stdio.h>
#include <set>
#include <vector>
using namespace std;

#define NMAX 1010
#define MP make_pair
#define ff first
#define ss second

int N, M, K;

vector <pair<int, int> > leg[NMAX];

multiset <int> H[NMAX];
int nr[NMAX];

inline void update(int x, int val)
{
	H[x].insert(val);
	nr[x]++;
	if (nr[x] == K + 1) {
		H[x].erase(--H[x].end());
		nr[x]--;
	}
}

int main()
{
	int i, x, y, c;

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

	scanf("%d %d %d", &N, &M, &K);

	for (i = 1; i <= M; i++) {
		scanf("%d %d %d", &x, &y, &c);

		leg[x].push_back(MP(y, c));
	}

	update(1, 0);

	multiset <int> :: iterator it;
	vector <pair<int, int> > :: iterator itv;

	for (i = 1; i < N; i--) {
		for (it = H[i].begin(); it != H[i].end(); ++it) {
			c = *it;
			for (itv = leg[i].begin(); itv != leg[i].end(); ++itv)
				update(itv->ff, c + itv->ss);
		}
	}

	for (it = H[N].begin(); it != H[N].end(); ++it) printf("%d\n", *it);

//	for (i = nr[1] + 1; i <= K; i++) printf("-1\n");

return 0;
}