flight_routes.cpp

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
const int maxn = 1e5 + 5, INF = 0x3f3f3f3f3f3f3f3f;

int cnt[maxn];
vector<pii> adj[maxn];
priority_queue<pii, vector<pii>, greater<pii>> pq;

int32_t main(){
	int n, m, k; cin >> n >> m >> k;
	for(int i = 0; i < m; i++){
		int a, b, c; cin >> a >> b >> c;
		adj[a].push_back({b, c});
	}

	pq.push({0, 1});
	while(pq.size()){
		auto[d, u] = pq.top(); pq.pop();
		if(cnt[u]==k) continue;
		cnt[u]++;

		if(u==n) cout << d << " ";

		for(auto[v, w] : adj[u]){
			pq.push({d+w, v});
		}
	}

	cout << '\n';
}