1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

import heapq

import sys

 

input = sys.stdin.readline

V, E = map(int, input().split())

K = int(input())

INF = 1e9

graph = [[] for _ in range(V + 1)]

distance = [INF] * (V + 1)

 

 

for _ in range(E):

    u, v, w = map(int, input().split())

    graph[u].append((v, w))

 

 

def dijkstra():

    q = []

    heapq.heappush(q, (0, K))

    distance[K] = 0

 

    while q:

        d, cur = heapq.heappop(q)

        if distance[cur] < d:

            continue

        for i in graph[cur]:

            temp = d + i[1]

            if temp < distance[i[0]]:

                distance[i[0]] = temp

                heapq.heappush(q, (temp, i[0]))

 

dijkstra()

 

for i in range(1, V + 1):

    if distance[i] == INF:

        print(‘INF’)

    else:

        print(distance[i])