main.cpp

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

using namespace std;

struct State {
    int steps;
    int days;
    int node;
    bool operator>(const State& other) const {
        if (steps != other.steps) {
            return steps > other.steps;
        }
        return days > other.days;
    }
};

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

    int n, m, start, target;
    if (!(cin >> n >> m >> start >> target)) {
        return 0;
    }
    vector<vector<pair<int, int>>> graph(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, days;
        cin >> u >> v >> days;
        graph[u].push_back({v, days});
        graph[v].push_back({u, days});
    }
    const pair<int, int> INF = {numeric_limits<int>::max() / 4, numeric_limits<int>::max() / 4};
    vector<pair<int, int>> dist(n + 1, INF);
    vector<int> prev(n + 1, -1);
    priority_queue<State, vector<State>, greater<State>> heap;
    dist[start] = {0, 0};
    heap.push({0, 0, start});
    while (!heap.empty()) {
        State cur = heap.top();
        heap.pop();
        if (make_pair(cur.steps, cur.days) != dist[cur.node]) {
            continue;
        }
        for (const auto& edge : graph[cur.node]) {
            int nxt = edge.first;
            int cand_steps = cur.steps + 1;
            int cand_days = cur.days + edge.second;
            pair<int, int> cand = {cand_steps, cand_days};
            if (cand < dist[nxt]) {
                dist[nxt] = cand;
                prev[nxt] = cur.node;
                heap.push({cand_steps, cand_days, nxt});
            }
        }
    }
    if (dist[target] == INF) {
        cout << "relay_count=-1\n";
        cout << "total_days=-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 << "relay_count=" << dist[target].first << "\n";
    cout << "total_days=" << dist[target].second << "\n";
    cout << "path=";
    for (size_t i = 0; i < path.size(); ++i) {
        if (i) {
            cout << "->";
        }
        cout << path[i];
    }
    cout << "\n";
    return 0;
}