4 5
1 2 2
1 3 5
2 3 1
2 4 4
3 4 1

0
2
3
4

import heapq
n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, w = map(int, input().split())
    graph[u].append((v, w))
dist = [float('inf')]*(n+1)
dist[1] = 0
heap = [(0, 1)]
while heap:
    d, node = heapq.heappop(heap)
    if d > dist[node]:
        continue
    for nxt, w in graph[node]:
        nd = d + w
        if nd < dist[nxt]:
            dist[nxt] = nd
            heapq.heappush(heap, (nd, nxt))
for i in range(1, n+1):
    print(dist[i] if dist[i] != float('inf') else 'INF')