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)
    graph = [[] for _ in range(n + 1)]
    for _ in range(m):
        u = next(it)
        v = next(it)
        days = next(it)
        graph[u].append((v, days))
        graph[v].append((u, days))
    inf = (10 ** 18, 10 ** 18)
    dist = [inf] * (n + 1)
    prev = [-1] * (n + 1)
    dist[start] = (0, 0)
    heap = [(0, 0, start)]
    while heap:
        steps, days, node = heapq.heappop(heap)
        if (steps, days) != dist[node]:
            continue
        for nxt, cost in graph[node]:
            cand = (steps + 1, days + cost)
            if cand < dist[nxt]:
                dist[nxt] = cand
                prev[nxt] = node
                heapq.heappush(heap, (cand[0], cand[1], nxt))
    if dist[target] == inf:
        return "relay_count=-1\ntotal_days=-1\npath=IMPOSSIBLE"
    path = []
    cur = target
    while cur != -1:
        path.append(cur)
        cur = prev[cur]
    path.reverse()
    return "\n".join(
        [
            f"relay_count={dist[target][0]}",
            f"total_days={dist[target][1]}",
            f"path={'->'.join(map(str, path))}",
        ]
    )


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