#include <vector>
#include <set>
#include <iostream>
#define int long long
const int inf = 1e17;
using namespace std;
 
vector<pair<int, int>> g[100005];
multiset<int> dist[100005];
 
int32_t main() {
	int n, m, k, ck = 0;
	cin >> n >> m >> k;
	for (int i = 0; i < m; ++i)
	{
		int u, v, w;
		cin >> u >> v >> w;
		g[u].push_back({ v,w });
	}
 
	multiset<pair<int, int>> s; //dist,node
	s.insert({ 0,1 });
	dist[1].insert(0);
 
	while (!s.empty())
	{
		pair<int, int> cur = *s.begin();
		s.erase(s.begin());
 
		if (!dist[cur.second].count(cur.first))
			continue; //removed this earlier
 
		for (auto x : g[cur.second])
		{
			int nd = cur.first + x.second;
			if (dist[x.first].size() < k) //space left
				dist[x.first].insert(nd), s.insert({ nd,x.first });
			else if (*dist[x.first].rbegin() > nd) //remove last
				dist[x.first].erase(dist[x.first].find(*dist[x.first].rbegin())),            
                                dist[x.first].insert(nd), s.insert({ nd,x.first });
		}
	}
 
	for (auto x : dist[n])
		cout << x << " ";
}