Challenge: Shortest Distances

Lab Python Intermediate 20 points

Read a graph with one-way roads that have lengths, and a start place. Print the shortest distance from the start to every place 0 … n − 1, or -1 if it can't be reached. Use Dijkstra with a heap.

Input

Line 1: n m. Then m lines a b w (a road from a to b of length w ≥ 0). Last line: the start.

Output

n numbers separated by spaces.

Example

Input

Output

0 3 1 4

Sample input available Sample output available

Editor

Python

Hints

Keep dist[] at infinity, except the start.

Pop the closest place from the heap; skip it if the popped distance is out of date.

Relax each road: if d + w < dist[b], update and push.

Solution explanation

The heap always gives the closest unfinished place, so once a place is popped with its true distance, it never improves again.

Show solution

import heapq
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b, w = map(int, input().split())
    g[a].append((b, w))
s = int(input())
INF = float("inf")
dist = [INF] * n
dist[s] = 0
heap = [(0, s)]
while heap:
    d, v = heapq.heappop(heap)
    if d > dist[v]:
        continue
    for w, c in g[v]:
        if d + c < dist[w]:
            dist[w] = d + c
            heapq.heappush(heap, (dist[w], w))
print(" ".join(str(d) if d != INF else "-1" for d in dist))

Output

Answer