## 1) Concise (abridged) problem statement

You are at junction **S** in an undirected graph with **N** junctions and **M** corridors.  
Each corridor \(i\) between \(A_i, B_i\) has:

- travel time \(T_i\) (seconds),
- initial temperature \(R_i\),
- heating speed \(P_i \ge 0\) (degrees per second).

Junctions always have temperature 0.

If you enter a corridor at time \(t\), then while traversing it your suit reaches the corridor’s current temperature, and the **maximum** temperature experienced on that corridor is at its end:
\[
\text{heat} = R_i + (t + T_i)\cdot P_i
\]
You have a suit that can withstand up to **H** degrees. There are **E** exit junctions.

Task: Find a path from **S** to any exit such that the **maximum heat encountered along the path** is minimized.  
If you can escape without exceeding **H**, output `YES`, that minimal possible maximum heat, and one corresponding path. Otherwise output `NO`.

Constraints: \(N \le 100\), \(M \le 10000\), values up to 10000.

---

## 2) Detailed editorial (solution idea)

### Key observation: “minimize the maximum” → binary search on the answer
Let’s denote by \(X\) a candidate value for the maximum heat your suit will ever experience.

If we fix \(X\), the question becomes:

> Is there a path from \(S\) to any exit such that **every used corridor** is traversed at a time where  
> \[
> R + (t + T)\cdot P \le X
> \]
> where \(t\) is the arrival time at the corridor’s start junction?

If the answer is “yes” for some \(X\), then it is also “yes” for any larger \(X\) (relaxing the constraint can’t hurt).  
So feasibility is monotone, enabling binary search for the minimum \(X\).

We only need to search \(X \in [0, H]\) because temperatures above \(H\) are fatal anyway; if the best \(X\) exceeds \(H\), escape is impossible.

---

### How to check feasibility for a fixed \(X\)

We need to know whether we can reach an exit. But the corridor condition depends on the **time** \(t\) when we start traversing it, and \(t\) depends on the chosen path.

For a fixed \(X\), we want the **earliest arrival times** at junctions, because arriving earlier can only help satisfy
\[
R + (t + T)\cdot P \le X
\]
(since \(P \ge 0\), higher \(t\) makes the left side larger or equal).

Thus, for a given \(X\), we run Dijkstra-like shortest path on travel time, **but only allow an edge** \(u\to v\) if it is safe when departing at time `dist[u]`:

- current time at \(u\): \(t = \text{dist}[u]\)
- edge parameters: \(T, R, P\)
- safe iff \(R + (t+T)\cdot P \le X\)

If safe, we can relax:
\[
\text{dist}[v] \leftarrow \min(\text{dist}[v],\ \text{dist}[u] + T)
\]

Because \(N \le 100\), the provided solution uses the \(O(N^2)\) Dijkstra variant (no priority queue), which is fast and simple and avoids overhead.

After computing distances, if any exit has finite distance, \(X\) is feasible. We can also store parents to reconstruct an actual path.

---

### Overall algorithm

1. Read input, build adjacency list of corridors.
2. Binary search \(X\) in \([0, H]\):
   - run `check(X)`:
     - Dijkstra earliest times with edge-allowed-by-\(X\)
     - if any exit reachable, return success and a reconstructed path
3. If no \(X\) feasible → `NO`
4. Else output `YES`, minimal feasible \(X\), and the path.

---

### Correctness sketch

- **Monotonicity**: If a path is safe under \(X\), it remains safe under any \(X' \ge X\). Hence binary search is valid.
- **Earliest times suffice**: With \(P \ge 0\), corridor heat at traversal end is nondecreasing in start time \(t\). If we can reach a node at time \(t_1\), reaching it later \(t_2 \ge t_1\) can only make future edges harder to satisfy, never easier. So considering minimal arrival times is optimal for feasibility.
- **Dijkstra validity**: Edge travel times \(T\) are nonnegative, and we relax by time, so standard Dijkstra reasoning applies within the subgraph of edges allowed by \(X\).

---

### Complexity

- `check(X)` with quadratic Dijkstra: \(O(N^2 + M)\) (the code is effectively \(O(N^2 + M)\)).
- Binary search over \([0,H]\): \(O(\log H)\) iterations, \(H \le 10000\) → ~14 iterations.
- Total: \(O((N^2+M)\log H)\), easily fine for given limits.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

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(auto x: a) {
        out << x << ' ';
    }
    return out;
};

const int64_t inf = 1e18;

int n, m, h, s, e;
vector<int> exits;

struct Edge {
    int to, t, r, p;
};

vector<vector<Edge>> adj;

void read() {
    cin >> n >> m >> h >> s >> e;
    adj.resize(n + 1);
    for(int i = 0; i < m; i++) {
        int a, b, t, r, p;
        cin >> a >> b >> t >> r >> p;
        adj[a].push_back({b, t, r, p});
        adj[b].push_back({a, t, r, p});
    }
    exits.resize(e);
    cin >> exits;
}

pair<bool, vector<int>> check(int64_t x) {
    vector<int64_t> dist(n + 1, inf);
    vector<int> parent(n + 1, -1);
    vector<bool> visited(n + 1, false);

    dist[s] = 0;

    for(int i = 0; i < n; i++) {
        int u = -1;
        for(int v = 1; v <= n; v++) {
            if(!visited[v] && (u == -1 || dist[v] < dist[u])) {
                u = v;
            }
        }

        if(u == -1 || dist[u] == inf) {
            break;
        }
        visited[u] = true;

        for(auto& [to, t, r, p]: adj[u]) {
            int64_t heat = r + (dist[u] + t) * (int64_t)p;
            if(heat <= x) {
                int64_t new_dist = dist[u] + t;
                if(new_dist < dist[to]) {
                    dist[to] = new_dist;
                    parent[to] = u;
                }
            }
        }
    }

    int best_exit = -1;
    for(int ex: exits) {
        if(dist[ex] < inf) {
            best_exit = ex;
            break;
        }
    }

    if(best_exit == -1) {
        return {false, {}};
    }

    vector<int> path;
    int cur = best_exit;
    while(cur != -1) {
        path.push_back(cur);
        cur = parent[cur];
    }
    reverse(path.begin(), path.end());

    return {true, path};
}

void solve() {
    // Let's binary search for the answer X. This means that we can now only
    // pass through a road (u, v) at time t, if r(u, v) + (t + time(u, v)) *
    // p(u, v) <= X. We want to figure out if there is a valid path from S to
    // any of the exists that satisfies this.
    //
    // The core observation is that after we have settled on X, we are
    // interested in the lowest time t we reach any vertex u. This can be done
    // with a Dijkstra, but by only allowing edges that don't violate the X
    // constraint. Note that the graph could be dense, so we opt for the
    // quadratic Dijkstra implementation.
    //
    // The time complexity is overall O(N^2 log MAX).

    int low = 0, high = h, mid, ret = -1;
    vector<int> best_path;

    while(low <= high) {
        mid = (low + high) / 2;
        auto [ok, path] = check(mid);
        if(ok) {
            ret = mid;
            best_path = path;
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    if(ret == -1) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
        cout << ret << "\n";
        cout << best_path.size() << " " << best_path << "\n";
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4) Python solution (same approach) with detailed comments

```python
import sys

INF = 10**30

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    # Read N, M, H, S, E
    n = int(next(it))
    m = int(next(it))
    h = int(next(it))
    s = int(next(it))
    e = int(next(it))

    # Build adjacency list (1-indexed)
    adj = [[] for _ in range(n + 1)]
    for _ in range(m):
        a = int(next(it))
        b = int(next(it))
        t = int(next(it))
        r = int(next(it))
        p = int(next(it))
        # undirected
        adj[a].append((b, t, r, p))
        adj[b].append((a, t, r, p))

    # Read exits
    exits = [int(next(it)) for _ in range(e)]

    def check(x: int):
        """
        Returns (ok, path)
        ok: True if reachable to any exit under max heat limit x
        path: one reconstructed path if ok else []
        """
        dist = [INF] * (n + 1)        # earliest arrival times
        parent = [-1] * (n + 1)       # for path reconstruction
        used = [False] * (n + 1)      # Dijkstra settled set

        dist[s] = 0

        # O(N^2) Dijkstra (N <= 100)
        for _ in range(n):
            u = -1
            best = INF
            # pick unvisited node with smallest dist
            for v in range(1, n + 1):
                if not used[v] and dist[v] < best:
                    best = dist[v]
                    u = v

            if u == -1:               # nothing reachable
                break

            used[u] = True

            # relax edges out of u if allowed by heat constraint
            du = dist[u]
            for to, t, r, p in adj[u]:
                # Heat at corridor end time (du + t):
                heat = r + (du + t) * p
                if heat <= x:
                    nd = du + t
                    if nd < dist[to]:
                        dist[to] = nd
                        parent[to] = u

        # Choose first reachable exit in input order
        exit_node = -1
        for ex in exits:
            if dist[ex] < INF:
                exit_node = ex
                break

        if exit_node == -1:
            return False, []

        # Reconstruct path S -> exit
        path = []
        cur = exit_node
        while cur != -1:
            path.append(cur)
            cur = parent[cur]
        path.reverse()
        return True, path

    # Binary search minimal feasible X in [0, H]
    lo, hi = 0, h
    best_x = -1
    best_path = []

    while lo <= hi:
        mid = (lo + hi) // 2
        ok, path = check(mid)
        if ok:
            best_x = mid
            best_path = path
            hi = mid - 1
        else:
            lo = mid + 1

    out = []
    if best_x == -1:
        out.append("NO\n")
    else:
        out.append("YES\n")
        out.append(f"{best_x}\n")
        out.append(str(len(best_path)) + " " + " ".join(map(str, best_path)) + "\n")

    sys.stdout.write("".join(out))

if __name__ == "__main__":
    solve()
```

---

## 5) Compressed editorial

Binary search the minimal maximum heat \(X \in [0,H]\).  
For fixed \(X\), compute earliest arrival times from \(S\) using Dijkstra on travel time, but allow an edge \((u\to v)\) only if
\[
R + (\text{dist}[u] + T)\cdot P \le X
\]
(because corridor temperature increases with time, \(P\ge 0\), so earliest arrivals are best).  
If any exit is reachable, \(X\) is feasible; store parents to reconstruct a path.  
Binary search yields the minimal feasible \(X\); if none exists → `NO`, else output `YES`, \(X\), and the path.