Shared code

#pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
 
#include "bits/stdc++.h"
 
//#define NDEBUG
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define pii pair<int, int>
#define all(m) m.begin(), m.end()
#define rall(m) m.rbegin(), m.rend()
#define uid uniform_int_distribution
#define timeStamp() std::chrono::steady_clock::now()
#define unify(m) sort(all(m)), m.erase(unique(all(m)), m.end());
#define duration_micro(a) chrono::duration_cast<chrono::microseconds>(a).count()
#define duration_milli(a) chrono::duration_cast<chrono::milliseconds>(a).count()
#define fast cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
using namespace std;
using str = string;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
mt19937 rnd(timeStamp().time_since_epoch().count());
mt19937_64 rndll(timeStamp().time_since_epoch().count());
template<typename T, typename U> bool chmin(T& a, const U& b) {return (T)b < a ? a = b, 1 : 0;}
template<typename T, typename U> bool chmax(T& a, const U& b) {return (T)b > a ? a = b, 1 : 0;}
struct custom_hash {static uint64_t xs(uint64_t x) {x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);} template<typename T> size_t operator()(T x) const {static const uint64_t C = timeStamp().time_since_epoch().count(); return xs(hash<T> {}(x) + C);}};
template<typename K> using uset = unordered_set<K, custom_hash>;
template<typename K, typename V> using umap = unordered_map<K, V, custom_hash>;
template<typename T1, typename T2> ostream& operator<<(ostream& out, const pair<T1, T2>& x) {return out << x.F << ' ' << x.S;}
template<typename T1, typename T2> istream& operator>>(istream& in, pair<T1, T2>& x) {return in >> x.F >> x.S;}
template<typename T, size_t N> istream& operator>>(istream& in, array<T, N>& a) {for (auto &x : a) in >> x; return in;}
template<typename T, size_t N> ostream& operator<<(ostream& out, const array<T, N>& a) {for (size_t i = 0; i < a.size(); ++i) {out << a[i]; if (i + 1 < a.size()) out << ' ';} return out;}
template<typename T> istream& operator>>(istream& in, vector<T>& a) {for (auto& x : a) in >> x; return in;}
template<typename T> ostream& operator<<(ostream& out, const vector<T>& a) {for (size_t i = 0; i < a.size(); ++i) {out << a[i]; if (i + 1 < a.size()) out << ' ';} return out;}
 
//Shortest path faster algorithm (aka Ford-Bellman with queue)
//Returns {dst, prv}
//dst - distances from cluster
//prv - previous nodes on shortest path from cluster
//dst[v] = inf if no path from cluster to v
//prv[v] = -1  if no path from cluster to v or v is in cluster
template<typename T>
pair<vector<T>, vector<int>> SPFA(vector<vector<pair<int, T>>>& g, const vector<int>& cluster, const T inf = numeric_limits<T>::max()) {
    const int n = g.size();
    vector<T> dst(n, inf);
    vector<int> pr(n, -1);
    vector<bool> inq(n);
    deque<int> que(cluster.begin(), cluster.end());
    for (int v : cluster) dst[v] = 0, inq[v] = 1;
    for (int v = 0; v < n; ++v) {
        shuffle(all(g[v]), rnd);
    }
    while (!que.empty()) {
        constexpr size_t MAGIC = 2;
        for (size_t i = 0; i < MAGIC && i + 1 < que.size(); ++i) {
            if (dst[que.back()] < dst[que[i]]) {
                swap(que.back(), que[i]);
                break;
            }
        }
        int v = que.front(); que.pop_front();
        inq[v] = 0;
        const T cur = dst[v];
        for (const auto& [h, d] : g[v]) {
            if (cur + d < dst[h]) {
                dst[h] = cur + d;
                pr[h] = v;
                if (!inq[h]) {
                    inq[h] = 1;
                    que.push_back(h);
                }
            }
        }
    }
    return {dst, pr};
}
 
int main() {
    fast;
    int a, k; cin >> a >> k;
    vector l(a, vector<pair<int, ll>>());
    for (int q = 0; q < k; ++q) {
        int x, y, c; cin >> x >> y >> c; --x, --y;
        l[x].emplace_back(y, c);
    }
    auto [dst, prv] = SPFA<ll>(l, {0});
    cout << dst;
}