<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

240. Runaway
time limit per test: 0.25 sec.
memory limit per test: 16384 KB
input: standard
output: standard



Damn!... How it can be happened to you - one of the best agents of FBI? You were imprisoned for crime; you were even not able to do. "Spy, traitor, murderer", they said. It sounds banal, but you were tripped up by some secret terroristical organization, and your friends (oh: ex-friends, I mean) didn't want to help you. You are alone: and it seems to be no ways to exit. There are only thick lead walls around you. You are in underground prison. Wait: what's happening? You hear screams and explosions nearby. What a hell!?... <Darkness over you and you lose consciousness>
You wake up and look around you. Doorlock of your cell is seriously damaged, so you can open the door easily. Wait: what a strange heat? You look into corridor and quickly realize situation. Prison was attacked from air by napalm-bomber. Napalm is still over prison, but it quickly burns its road down. The temperature everywhere in prison is slowly raising, in different parts of prison speed of heating is not the same, but everywhere it is non-negative value. You know, that corridors of a prison have toral shape. It was offered by D. Kurov scientist just to check his geometry skills. But it does not matter to you, and the only thing, important to you now, is that there are several exits from this prison. Fortunately, you know the map of prison (it is on the wall of corridor, marked as "Evacuation Plan"). Also you know the approximate points of falling napalm bombs (you heard that information in moment of losing consciousness from internal prison communicator), so you can predict speeds of heat growing for all corridors. You have already got evacuation fire-resistant suit which can resist heat of H degrees Centigrade (if temperature is greater than H, your character will die). You must construct a way to get out from prison in such a manner such that maximal heat of your suit on this way is minimal possible (temperature of suit is always equal to current temperature in corridor).
Prison consists of M corridors and N corridor junctions. Also E of N junctions are exits, and you are initially located at junction number S (junctions are numbered from 1 to N). Corridors have their initial heat Ri, and non-negative speed of heat raising Pi (in degrees by second), also corridors have lengths Ti - time you need to run over them (in seconds). You must consider that junctions always have temperature 0.

Input
On first line of input file there are only numbers N, M, H, S and E (1<=N<=100; 1<=S,E<=N; 1<=M,H<=10000). Next M lines describe prison corridors, I-th line of them containing numbers Ai, Bi, Ti, Ri and Pi, where A and B are numbers of junctions, connected by corresponding corridor (1<=Ai,Bi<=N; 1<=Ti<=10000; 0<=Ri,Pi<=10000; Ai<>Bi). At next line there are exactly E numbers Fi - numbers of junctions, which are exits (1<=Fi<=N). There are no multiple corridors between any two junctions. All corridors are two-sided. All numbers are integers.

Output
On the first line must be exactly one word "YES" (if you can stay alive and get out from prison) or "NO" (in other case). In case of positive answer, second line of output file must contain maximal heat of suit on the best way, then on the third line there must be the best way itself (if there are many best ways, you can output any one of them) in form: Z - number of junctions in the way, then Z numbers - numbers of junctions in best way in order of passing it (start junction assumed to be passed, even if you make no moves).

Sample test(s)

Input
4 4 10 4 1
1 2 1 0 1
1 3 2 1 0
1 4 3 0 1
2 3 4 2 2
3

Output
YES
3
3 4 1 3

<|response|>
## 1) Abridged problem statement (concise)

You are in an undirected graph with **N** junctions and **M** corridors. Start at junction **S**. There are **E** exit junctions.

Each corridor has:
- travel time \(T\) (seconds),
- initial temperature \(R\),
- heating speed \(P \ge 0\) (degrees/second).

Junctions always have temperature **0**.

If you start traversing a corridor at time \(t\), then the **maximum** temperature your suit reaches on that corridor occurs at the end:
\[
\text{heat} = R + (t + T)\cdot P
\]
Your suit can withstand up to **H** degrees (strictly greater than \(H\) kills you).

Find a path from **S** to any exit minimizing the **maximum heat encountered** along the path.  
If escaping within \(H\) is possible, output `YES`, that minimal possible maximum heat, and one such path; otherwise output `NO`.

---

## 2) Key observations

1. **“Minimize the maximum” suggests binary search on the answer.**  
   Let \(X\) be a candidate bound on the maximum heat encountered. We can ask: *Is there a path to an exit such that every traversed corridor never exceeds heat \(X\)?*

2. **Feasibility is monotone in \(X\).**  
   If escape is possible with bound \(X\), it’s also possible with any larger \(X'\ge X\).  
   So we can binary search the minimum feasible \(X\) in \([0, H]\).

3. **For a fixed \(X\), arriving earlier is always better.**  
   Corridor heat at traversal end is:
   \[
   R + (t+T)P
   \]
   Since \(P \ge 0\), increasing \(t\) cannot decrease heat. So to test feasibility for \(X\), we only need to consider **earliest arrival times** at junctions.

4. **Feasibility check becomes a shortest path problem with edge constraints.**  
   For a fixed \(X\), from a node \(u\) reached at earliest time \(\text{dist}[u]\), you may traverse edge \((u\to v)\) only if:
   \[
   R + (\text{dist}[u] + T)\cdot P \le X
   \]
   If allowed, you can relax:
   \[
   \text{dist}[v] = \min(\text{dist}[v], \text{dist}[u] + T)
   \]
   This is Dijkstra on travel time, with “allowed edge” depending on current earliest time.

---

## 3) Full solution approach

### Step A — Build the graph
Store each corridor as an undirected edge with parameters \((to, T, R, P)\).

### Step B — `check(X)` feasibility test
Goal: determine if some exit is reachable without ever exceeding heat \(X\).

Run Dijkstra-like algorithm for earliest arrival time:
- `dist[v]` = earliest time you can reach junction `v`.
- Start: `dist[S] = 0`.
- When at junction `u`, consider each corridor `u -> to`:
  - compute `heat = R + (dist[u] + T) * P`
  - if `heat <= X`, you may traverse it and relax `dist[to]`.

Keep `parent[to] = u` when relaxing to reconstruct a path.

If any exit node ends with finite distance, `check(X)` is feasible; reconstruct and return the path.

Because \(N \le 100\), a simple \(O(N^2 + M)\) Dijkstra (no priority queue) is fast and avoids overhead.

### Step C — Binary search the minimal feasible \(X\)
Search \(X \in [0, H]\):
- If `check(mid)` is feasible, record it and try smaller (`hi = mid - 1`).
- Otherwise try larger (`lo = mid + 1`).

If no \(X \le H\) is feasible: output `NO`.  
Otherwise output `YES`, best \(X\), and the found path.

### Complexity
- Each `check(X)`: \(O(N^2 + M)\).
- Binary search: \(O(\log H)\) iterations, with \(H \le 10000\) (~14).
- Total: \(O((N^2 + M)\log H)\), easily within limits.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

static const long long INF = (long long)4e18;

struct Edge {
    int to;
    int T;   // travel time
    int R;   // initial heat
    int P;   // heating speed (>=0)
};

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

    int N, M, H, S, E;
    cin >> N >> M >> H >> S >> E;

    vector<vector<Edge>> adj(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});
    }

    vector<int> exits(E);
    for (int i = 0; i < E; i++) cin >> exits[i];

    // Feasibility check for a given max-heat bound X.
    // Returns {ok, path}. If ok==true, path is a sequence of vertices from S to an exit.
    auto check = [&](long long X) -> pair<bool, vector<int>> {
        vector<long long> dist(N + 1, INF); // earliest arrival times
        vector<int> parent(N + 1, -1);      // for reconstructing path
        vector<char> used(N + 1, 0);        // Dijkstra "visited"/settled

        dist[S] = 0;

        // O(N^2) Dijkstra (fine for N<=100)
        for (int it = 0; it < N; it++) {
            int u = -1;
            for (int v = 1; v <= N; v++) {
                if (!used[v] && dist[v] < INF && (u == -1 || dist[v] < dist[u])) {
                    u = v;
                }
            }
            if (u == -1) break; // nothing else reachable

            used[u] = 1;

            // Relax outgoing edges that are safe under bound X
            for (const auto &ed : adj[u]) {
                int v = ed.to;
                long long tstart = dist[u];

                // Maximum heat on this corridor occurs at the end time (tstart + T).
                long long heat = (long long)ed.R + (tstart + ed.T) * (long long)ed.P;

                // Only traverse if heat never exceeds X (here that's the end-time value).
                if (heat <= X) {
                    long long nd = tstart + ed.T;
                    if (nd < dist[v]) {
                        dist[v] = nd;
                        parent[v] = u;
                    }
                }
            }
        }

        // Pick any reachable exit (first in input order).
        int exitNode = -1;
        for (int ex : exits) {
            if (dist[ex] < INF) {
                exitNode = ex;
                break;
            }
        }
        if (exitNode == -1) return {false, {}};

        // Reconstruct path S -> exitNode using parent pointers.
        vector<int> path;
        for (int cur = exitNode; cur != -1; cur = parent[cur]) path.push_back(cur);
        reverse(path.begin(), path.end());
        return {true, path};
    };

    // Binary search the minimal feasible X within [0, H].
    int lo = 0, hi = H;
    int bestX = -1;
    vector<int> bestPath;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        auto [ok, path] = check(mid);
        if (ok) {
            bestX = mid;
            bestPath = path;
            hi = mid - 1;   // try smaller max heat
        } else {
            lo = mid + 1;   // need larger max heat
        }
    }

    if (bestX == -1) {
        cout << "NO\n";
    } else {
        cout << "YES\n";
        cout << bestX << "\n";
        cout << bestPath.size();
        for (int v : bestPath) cout << " " << v;
        cout << "\n";
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

INF = 10**30

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

    N = int(next(it))
    M = int(next(it))
    H = int(next(it))
    S = int(next(it))
    E = int(next(it))

    # adjacency list: adj[u] contains (v, T, R, P)
    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))
        adj[A].append((B, T, R, P))
        adj[B].append((A, T, R, P))

    exits = [int(next(it)) for _ in range(E)]

    def check(X: int):
        """
        Feasibility for max-heat bound X.
        Returns (ok, path). If ok, path is a list of vertices from S to an exit.
        """
        dist = [INF] * (N + 1)     # earliest arrival times
        parent = [-1] * (N + 1)    # for path reconstruction
        used = [False] * (N + 1)   # settled nodes in O(N^2) Dijkstra

        dist[S] = 0

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

            used[u] = True
            du = dist[u]

            for to, T, R, P in adj[u]:
                # Max heat on corridor occurs at 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

        exit_node = -1
        for ex in exits:
            if dist[ex] < INF:
                exit_node = ex
                break

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

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

    # Binary search answer 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

    if best_x == -1:
        sys.stdout.write("NO\n")
    else:
        sys.stdout.write("YES\n")
        sys.stdout.write(str(best_x) + "\n")
        sys.stdout.write(str(len(best_path)) + " " + " ".join(map(str, best_path)) + "\n")

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

