K menores caminhos

#include <bits/stdc++.h>
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define endl '\n'

using namespace std;

using ll = long long;
using pii = pair<int, int>;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int MOD = 1000000007;
const int dx[] = { 0, 0, -1, 1, 1, -1,  1, -1};
const int dy[] = {-1, 1,  0, 0, 1, -1, -1,  1};
const int MAXN = 200010;
#include <bits/stdc++.h>
using namespace std;
namespace Dijkstra{
  typedef long long T;
  typedef pair<T, int> pti;
  vector<vector<pti>> adj;
  int n;
  void init(int n1){
    n = n1;
    adj.assign(n, vector<pti>());
  }
  void addEdge(int from, int to, T w){
    adj[from].emplace_back(w, to);
  }
  vector<T> solve(int s, int t, int k){
    vector<vector<T>> dist(n, vector<T>());
    priority_queue<pti, vector<pti>, greater<pti>> st;
    st.emplace(0, s);
    while(!st.empty()){
      auto [wu, u] = st.top();
      st.pop();
      if(dist[u].size() == k) continue;
      dist[u].push_back(wu);
      for(auto [w, to]: adj[u]){
        st.emplace(wu + w, to);
      }
    }
    return dist[t];
  }
};

int main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);

  int n, m, k;
  cin >> n >> m >> k;

  Dijkstra::init(n);

  for(int i=0; i<m; i++){
    int a, b, c;
    cin >> a >> b >> c;
    a--; b--;
    Dijkstra::addEdge(a, b, c);
  }
  vector<ll> ans = Dijkstra::solve(0, n-1, k);
  for(ll x: ans)
    cout << x << " ";
  cout << endl;
  return 0;
}