Shared code

#include <bits/stdc++.h>

#include <set>
#include <array>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <vector>
#include <ext/pb_ds/assoc_container.hpp>

#include <vector>
#include <chrono>

namespace felix {

class random_t {
public:
	unsigned long long state, seed;

	random_t() : random_t(std::chrono::steady_clock::now().time_since_epoch().count()) {}

	random_t(unsigned long long s) : state(s), seed(s) {}

	inline void set_seed(unsigned long long s) {
		state = seed = s;
	}

	inline void reset() {
		set_seed(seed);
	}

	inline unsigned long long next() {
		state += 0x9e3779b97f4a7c15;
		unsigned long long result = state;
		result = (result ^ (result >> 30)) * 0xbf58476d1ce4e5b9;
		result = (result ^ (result >> 27)) * 0x94d049bb133111eb;
		return result ^ (result >> 31);
	}

	inline unsigned long long next(unsigned long long a) {
		return next() % a;
	}

	inline unsigned long long next(unsigned long long a, unsigned long long b) {
		return a + next(b - a + 1);
	}

	inline long double nextDouble() {
		return ((unsigned int) next()) / 4294967295.0;
	}

	inline long double nextDouble(long double a) {
		return nextDouble() * a;
	}

	inline long double nextDouble(long double a, long double b) {
		return a + nextDouble() * (b - a);
	}

	template<class T>
	void shuffle(std::vector<T>& a) {
		for(int i = int(a.size()) - 1; i; --i)
			std::swap(a[i], a[next(i + 1)]);
	}
};

random_t rnd;

} // namespace felix


namespace felix {

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<class T> using pair2 = std::pair<T, T>;
using pii = pair2<int>;
using pll = pair2<ll>;
using pdd = pair2<ld>;
using tiii = std::tuple<int, int, int>;
template<class T, size_t S> using ar = std::array<T, S>;
template<class T, class U = std::less<T>> using mset = std::multiset<T, U>;
template<class T> using vt = std::vector<T>;
template<class T, class Comp = std::less<T>> using oset = __gnu_pbds::tree<T, __gnu_pbds::null_type, Comp, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;
template<class T> using omset = oset<T, std::less_equal<T>>;

struct splitmix64_hash {
	static ull splitmix64(ull x) {
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
 
	ull operator()(ull x) const {
		static const ull FIXED_RANDOM = rnd.next();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template<class T, class U, class H = splitmix64_hash> using hash_map = __gnu_pbds::gp_hash_table<T, U, H>;
template<class T, class H = splitmix64_hash> using hash_set = hash_map<T, __gnu_pbds::null_type, H>;

} // namespace felix


#include <iostream>
#include <cstring>

namespace felix {

const std::string NONE = "\033[m", RED = "\033[0;32;31m", LIGHT_RED = "\033[1;31m", GREEN = "\033[0;32;32m", LIGHT_GREEN = "\033[1;32m", BLUE = "\033[0;32;34m", LIGHT_BLUE = "\033[1;34m", DARK_GRAY = "\033[1;30m", CYAN = "\033[0;36m", LIGHT_CYAN = "\033[1;36m", PURPLE = "\033[0;35m", LIGHT_PURPLE = "\033[1;35m", BROWN = "\033[0;33m", YELLOW = "\033[1;33m", LIGHT_GRAY = "\033[0;37m", WHITE = "\033[1;37m";
template<class c> struct rge { c b, e; };
template<class c> rge<c> range(c i, c j) { return rge<c>{i, j}; }
template<class c> auto dud(c* x)->decltype(std::cerr << *x, 0);
template<class c> char dud(...);
struct debug {
#ifdef LOCAL
	~debug() { std::cerr << std::endl; }
	template<class c> typename std::enable_if<sizeof dud<c>(0) != 1, debug&>::type operator<<(c i) { std::cerr << std::boolalpha << i; return *this; }
	template<class c> typename std::enable_if<sizeof dud<c>(0) == 1, debug&>::type operator<<(c i) { return *this << range(begin(i), end(i)); }
	template<class c, class b> debug& operator<<(std::pair<b, c> d) { return *this << "(" << d.first << ", " << d.second << ")"; }
	template<class a, class b, class c> debug& operator<<(std::tuple<a, b, c> tp) { return *this << "(" << std::get<0>(tp) << ", " << std::get<1>(tp) << ", " << std::get<2>(tp) << ")"; };
	template<class a, class b, class c, class d> debug& operator<<(std::tuple<a, b, c, d> tp) { return *this << "(" << std::get<0>(tp) << ", " << std::get<1>(tp) << ", " << std::get<2>(tp) << ", " << std::get<3>(tp) << ")"; };
	template<class c> debug& operator<<(rge<c> d) {
		*this << "{";
		for(auto it = d.b; it != d.e; ++it)
			*this << ", " + 2 * (it == d.b) << *it;
		return *this << "}";
	}
#else
	template<class c> debug& operator<<(const c&) { return *this; }
#endif
};
#define show(...) "" << LIGHT_RED << " [" << NONE << #__VA_ARGS__ ": " << (__VA_ARGS__) << LIGHT_RED << "] " << NONE << ""

} // namespace felix

using namespace std;
using namespace felix;

const ll LINF = 1e18L;

int main(int argc, char* argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vt<vt<pair<int, ll>>> adj(n);
	for(int i = 0; i < m; ++i) {
		int u, v, c;
		cin >> u >> v >> c;
		--u, --v;
		adj[u].emplace_back(v, c);
	}
	vt<vt<ll>> dist(n);
	for(int i = 0; i < n; ++i) {
		dist[i].reserve(k + 1);
		dist[i].push_back(LINF);
	}
	dist[0][0] = 0;
	priority_queue<pair<ll, int>, vt<pair<ll, int>>, greater<pair<ll, int>>> pq;
	pq.emplace(0, 0);
	while(!pq.empty()) {
		auto [cur, u] = pq.top();
		pq.pop();
		if(lower_bound(dist[u].begin(), dist[u].end(), cur) == dist[u].end()) {
			continue;
		}
		for(auto& [v, d] : adj[u]) {
			ll w = cur + d;
			bool removed = false;
			dist[v].insert(lower_bound(dist[v].begin(), dist[v].end(), w), w);
			while((int) dist[v].size() > k) {
				if(dist[v].back() == w) {
					removed = true;
				}
				dist[v].pop_back();
			}
			if(removed) {
				continue;
			}
			pq.emplace(w, v);
		}
	}
	for(int i = 0; i < k; ++i) {
		cout << dist[n - 1][i] << " \n"[i == k - 1];
	}
	return 0;
}