main.cpp

#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <tuple>
#include <utility>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, start, target, load;
    if (!(cin >> n >> m >> start >> target >> load)) {
        return 0;
    }
    vector<vector<tuple<int, int, int>>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, dist, capacity, risk;
        cin >> u >> v >> dist >> capacity >> risk;
        if (capacity < load) {
            continue;
        }
        graph[u].push_back({v, dist, risk});
        graph[v].push_back({u, dist, risk});
    }

    const long long INF = numeric_limits<long long>::max() / 4;
    vector<long long> best_dist(n + 1, INF), best_risk(n + 1, INF);
    vector<int> prev(n + 1, -1);
    using State = tuple<long long, long long, int>;
    priority_queue<State, vector<State>, greater<State>> pq;
    best_dist[start] = 0;
    best_risk[start] = 0;
    pq.push({0, 0, start});

    while (!pq.empty()) {
        auto [cur_dist, cur_risk, node] = pq.top();
        pq.pop();
        if (cur_dist != best_dist[node] || cur_risk != best_risk[node]) {
            continue;
        }
        for (auto [nxt, dist, risk] : graph[node]) {
            long long nd = cur_dist + dist;
            long long nr = cur_risk + risk;
            if (nd < best_dist[nxt] || (nd == best_dist[nxt] && nr < best_risk[nxt])) {
                best_dist[nxt] = nd;
                best_risk[nxt] = nr;
                prev[nxt] = node;
                pq.push({nd, nr, nxt});
            }
        }
    }

    if (best_dist[target] == INF) {
        cout << "min_distance=-1\n";
        cout << "total_risk=-1\n";
        cout << "path=IMPOSSIBLE\n";
        return 0;
    }

    vector<int> path;
    for (int cur = target; cur != -1; cur = prev[cur]) {
        path.push_back(cur);
    }
    reverse(path.begin(), path.end());
    cout << "min_distance=" << best_dist[target] << "\n";
    cout << "total_risk=" << best_risk[target] << "\n";
    cout << "path=";
    for (size_t i = 0; i < path.size(); ++i) {
        if (i) {
            cout << "->";
        }
        cout << path[i];
    }
    cout << "\n";
    return 0;
}