main.py

import heapq
import sys


def solve(data: str) -> str:
    tokens = list(map(int, data.split()))
    if not tokens:
        return ""
    it = iter(tokens)
    n = next(it)
    m = next(it)
    start = next(it)
    target = next(it)
    load = next(it)
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = next(it)
        v = next(it)
        dist = next(it)
        capacity = next(it)
        risk = next(it)
        if capacity < load:
            continue
        graph[u].append((v, dist, risk))
        graph[v].append((u, dist, risk))
    inf = 10 ** 18
    best_dist = [inf] * (n + 1)
    best_risk = [inf] * (n + 1)
    prev = [-1] * (n + 1)
    best_dist[start] = 0
    best_risk[start] = 0
    heap = [(0, 0, start)]
    while heap:
        cur_dist, cur_risk, node = heapq.heappop(heap)
        if cur_dist != best_dist[node] or cur_risk != best_risk[node]:
            continue
        for nxt, dist, risk in graph[node]:
            nd = cur_dist + dist
            nr = cur_risk + risk
            if nd < best_dist[nxt] or (nd == best_dist[nxt] and nr < best_risk[nxt]):
                best_dist[nxt] = nd
                best_risk[nxt] = nr
                prev[nxt] = node
                heapq.heappush(heap, (nd, nr, nxt))
    if best_dist[target] == inf:
        return "min_distance=-1\ntotal_risk=-1\npath=IMPOSSIBLE"
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = prev[cur]
    path.reverse()
    return "\n".join(
        [
            f"min_distance={best_dist[target]}",
            f"total_risk={best_risk[target]}",
            f"path={'->'.join(map(str, path))}",
        ]
    )


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")