#競プロ典型90問 13日目 https://twitter.com/e869120/status/1381739128291614720

solve_day13.py

import heapq
from typing import List, Tuple


def calc_costs(N: int, MAP: List[Tuple[int, int]], start: int) -> List[int]:
    """
    指定された都市から各都市への最小コストを計算する

    MAP: list of { index: 都市, value: (行先の都市, コスト) }
    """
    costs = [-1] * N
    # queueの要素は (その都市への最小コスト, 都市)
    # コストの小さい順に取り出すためにコストをtupleの先頭にもってくる
    queue = [(0, start)]
    heapq.heapify(queue)
    while len(queue) > 0:
        cost, city = heapq.heappop(queue)
        if costs[city] >= 0:
            continue
        costs[city] = cost
        for next_city, next_cost in MAP[city]:
            if costs[next_city] < 0:
                heapq.heappush(queue, (cost + next_cost, next_city))
    return costs


def solve(N, MAP):
    costs_from_start = calc_costs(N, MAP, 0)
    costs_from_goal = calc_costs(N, MAP, N - 1)
    for day in range(N):
        print(costs_from_start[day] + costs_from_goal[day])


def main():
    N, M = [int(v) for v in input().split(' ')]
    MAP = [[] for v in range(N)]
    for _ in range(M):
        a, b, c = [int(v) for v in input().split(' ')]
        MAP[a - 1].append((b - 1, c))
        MAP[b - 1].append((a - 1, c))

    solve(N, MAP)


if __name__ == "__main__":
    main()