CSES – Flight Routes

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
using namespace std;
//declare
const int maxn = 1e5+5;
int n,m,k;
vector<pii> G[maxn];
vector<int> dis[maxn];
//
void dijkstra(int start){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,start});
    while(!pq.empty()){
        auto [w, cur] = pq.top(); pq.pop();
        if(dis[cur].size() == k) continue;
        dis[cur].push_back(w);
        for(auto [adj, weight] : G[cur]){
            pq.push({dis[cur].back() + weight, adj});
        }
    }
}
signed main(){
    fastio;
    cin>>n>>m>>k;
    for(int i=0;i<m;i++){
        int a,b,c; cin>>a>>b>>c;
        G[a].push_back({b,c});
    }
    dijkstra(1);
    for(int i: dis[n]) cout<<i<<" ";
    cout<<"\n";
    return 0;
}