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


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