openol C 47

#include <bits/stdc++.h>
// tiom4eg's precompiler options
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
// IO settings
#define fastIO ios_base::sync_with_stdio(false); cin.tie(0)
// Quick types
#define ll long long
#define ld long double
#define ull unsigned long long
#define pii pair <int, int>
#define vi vector <int>
#define mi vector <vector <int>>
// Quick functions
#define endl "\n"
#define F first
#define S second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define pb push_back
#define mp make_pair
// Quick fors
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORS(i, a, b, c) for (int i = a; i < b; i += c)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)
#define EACH(e, a) for (auto& e : a)
// Pragmas
#ifndef TIOM4EG
#pragma GCC optimize("O3,unroll-loops") // let the chaos begin!
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt,tune=native")
#pragma GCC comment(linker, "/stack:200000000")
#endif
// PBDS
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update>
#define ook order_of_key
#define fbo find_by_order
using namespace __gnu_pbds;
// POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS POGGERS
using namespace std;
mt19937 rng(chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now().time_since_epoch()).count());
#define int long long
const int INF = 1e9 + 7, INFLL = 1e18 + 7, MD = 998244353, R = 1 << 18, MOD = 1e9 + 7, MAX = 500009, LG = 20, B = 31, S = 10008;

#define min(a, b) ((a < b) ? (a) : (b))
#define max(a, b) ((a > b) ? (a) : (b))

int b[MAX], e[MAX], w[MAX], nx[MAX];
vi fr[MAX];

signed main() {
    fastIO;
    int n, m, t; cin >> n >> m >> t;
    if (t < 3) {
        int t = 0;
        vi used(m), d(n, INFLL);
        FOR(i, 0, m) cin >> b[i] >> e[i] >> w[i] >> nx[i], --e[i], --nx[i], fr[--b[i]].pb(i);
        set <pii> q;
        d[0] = 0, q.insert({0, 0});
        auto relax = [&](int v) {
            ++t;
            int c = d[b[v]], l = w[v];
            while (v != -2 && used[v] != t) {
                used[v] = t;
                c += l, l = (l ? l - 1 : l);
                if (d[e[v]] > c) {
                    q.erase({d[e[v]], e[v]});
                    d[e[v]] = c;
                    q.insert({d[e[v]], e[v]});
                }
                v = nx[v];
            }
        };
        while (!q.empty()) {
            int x = q.begin()->S;
            q.erase(q.begin());
            EACH(v, fr[x]) relax(v);
        }
        EACH(x, d) cout << (x == INFLL ? -1 : x) << ' ';
        return 0;
    }
    if (t == 3) {
        vector <pii> g[n];
        FOR(i, 0, m) {
            int u, v, w, d; cin >> u >> v >> w >> d, --u, --v;
            g[u].pb({v, w});
        }
        vi d(n, INFLL);
        priority_queue <pii> q;
        d[0] = 0, q.push({0, 0});
        while (!q.empty()) {
            auto [w, v] = q.top();
            q.pop();
            if (-w > d[v]) continue;
            for (auto& [u, z] : g[v]) if (d[u] > d[v] + z) d[u] = d[v] + z, q.push({-d[u], u});
        }
        FOR(i, 0, n) cout << (d[i] == INFLL ? -1 : d[i]) << ' ';
        return 0;
    }
    if (t == 4) {
        vector <pii> edges(m);
        vi d(n, INF), used(m), g[n];
        FOR(i, 0, m) {
            int u, v, w, d; cin >> u >> v >> w >> d, --u, --v, --d;
            edges[i] = {v, d}, g[u].pb(i);
        }
        deque <int> q;
        d[0] = 0, q.pb(0);
        while (!q.empty()) {
            int v = q.front(); q.pop_front();
            EACH(id, g[v]) while (id != -2 && !used[id]) {
                if (d[edges[id].F] == INF) d[edges[id].F] = d[v] + 1, q.pb(edges[id].F);
                used[id] = 1, id = edges[id].S;
            }
        }
        FOR(i, 0, n) cout << (d[i] == INF ? -1 : d[i]) << ' ';
        return 0;
    }
    if (t == 5) {
        vi used(11 * m + 1), d(11 * m + 1, INFLL);
        FOR(i, 0, m) cin >> b[i] >> e[i] >> w[i] >> nx[i], --e[i], --nx[i], fr[--b[i]].pb(i);
        set <pii> q;
        d[11 * m] = 0, nx[m] = -2;
        q.insert({0, 11 * m});
        /*auto relax = [&](int v) {
            //cout << "-------\n" << v << ' ' << d[v] << endl;
            used[v] = ++t;
            int c = d[v], l = max(0, v % 11 - 1);
            v /= 11, v = nx[v];
            while (v != -2 && used[11 * v + l] != t) {
                used[11 * v + l] = t, c += l;
                //cout << v << ' ' << c << ' ' << l << endl;
                if (d[11 * v + l] <= c) break;
                q.erase({d[11 * v + l], 11 * v + l});
                d[11 * v + l] = c;
                q.insert({d[11 * v + l], 11 * v + l});
                l = (l ? l - 1 : l), v = nx[v];
            }
        };*/
        while (!q.empty()) {
            int x = q.begin()->S, v = x / 11, z = x % 11;
            q.erase(q.begin());
            if (nx[v] != -2) {
                //relax(x);
                if (d[11 * nx[v] + max(0, z - 1)] > d[x] + max(0, z - 1)) {
                    q.erase({d[11 * nx[v] + max(0, z - 1)], 11 * nx[v] + max(0, z - 1)});
                    d[11 * nx[v] + max(0, z - 1)] = d[x] + max(0, z - 1);
                    q.insert({d[11 * nx[v] + max(0, z - 1)], 11 * nx[v] + max(0, z - 1)});
                }
            }
            EACH(u, fr[e[v]]) {
                if (u == nx[v]) continue;
                if (d[11 * u + w[u]] <= d[x] + w[u]) break;
                q.erase({d[11 * u + w[u]], 11 * u + w[u]});
                d[11 * u + w[u]] = d[x] + w[u];
                q.insert({d[11 * u + w[u]], 11 * u + w[u]});
            }
        }
        vi ans(n, INFLL);
        FOR(i, 0, 11 * m + 1) ans[e[i / 11]] = min(ans[e[i / 11]], d[i]);
        FOR(i, 0, n) cout << (ans[i] == INFLL ? -1 : ans[i]) << ' ';
    }
}