Shared code

#include<bits/stdc++.h>
//#include <algorithm>
//#include <iostream>
//#include <iterator>
//#include <string.h>
//#include <utility>
//#include <vector>
//#include <map>

//#pragma GCC optimize "trapv"

#define debug(...) cout<<#__VA_ARGS__<<" = "; print(__VA_ARGS__);
#define dracarys ios_base::sync_with_stdio(false);cin.tie(NULL)

#define TEST_CASE int  t;cin>>t;while(t--)
#define For(i,a,b) for(long long  i=a;i<b;i++)

#define all(v) v.begin(),v.end()
#define pb push_back

#define int long long
#define endl "\n"

#define S second
#define F first



using namespace std;
const long long MOD = 1e9 + 7;

void print()  {    cout<<endl;  }
void printArray()  {    return;  }
void read() { return; }

template<typename T , typename... Args>  void print(T a , Args... arg)    {    cout << a << " " ;    print(arg...);    }

template<typename T , typename... Args> void read(T &a , Args&... arg) {   cin >> a;   read(arg...);   }

template<typename T,typename... Args> void read(vector<T>&v , Args&... arg) {  for(auto &i : v)  cin>>i;  read(arg...);  }

template<typename T,typename... Args> void printArray(vector<T>&v, Args&... arg) {   for(auto i : v)     cout<<i<<" ";   cout<<endl;  printArray(arg...);    }

const long long inf = 1e18;
long long n,m,k;
vector<vector<pair<int,int>>>g;
vector<multiset<int>>dis;


void getPaths()
{
        dis[1].insert(0);
        multiset<pair<int,int>>pq;
        pq.insert({0,1});
        while(!pq.empty())
        {
                pair<int,int>q = *(pq.begin());
                pq.erase(pq.begin());
                long long u = q.S, w = q.F;
                for(auto p : g[u])
                {
                        long long v = p.F, wt = p.S,x = w + wt;
                        if(dis[v].size() < k)
                        {
                                dis[v].insert(x);
                                pq.insert({x,v});
                        }
                        else
                        {
                                for(auto i = dis[v].rbegin(); i != dis[v].rend(); ++i)
                                {
                                        long long y = *i;
                                        if(y > x)
                                        {
                                                pq.erase(pq.find({y,v}));
                                                dis[v].erase(dis[v].find(y));
                                                dis[v].insert(x);
                                                pq.insert({x,v});
                                                break;
                                        }
                                        else break;
                                }
                        }
                }
        }
}

void runCase_()
{
        scanf("%lld%lld%lld",&n,&m,&k);
        g.resize(n+1); dis.resize(n+1);
        For(i,0,m)
        {
                long long a,b,c;
                scanf("%lld%lld%lld",&a,&b,&c);
                g[a].pb({b,c});
        }
        getPaths();
        for(auto i : dis[n])  printf("%lld ",i);
}


signed main()
{
//     dracarys;
//     TEST_CASE
     runCase_();
     return 0;
}

/** TEST CASES HERE **/
/*

*/