import heapq





class Edge:

    def __init__(self, dst, weight):

        self.dst, self.weight = dst, weight



    def __lt__(self, e):

        return self.weight > e.weight





class Graph:

    def __init__(self, V):

        self.V = V

        self.E = [[] for _ in range(V)]



    def add_edge(self, src, dst, weight):

        self.E[src].append(Edge(dst, weight))





class ShortestPath:

    """Dijkstra's algorithm : find the shortest path from a vertex

       Complexity: O(E + log(V))

       used in GRL1A(AOJ)

    """



    def __init__(self, G, INF=10**9):

        """ V: the number of vertexes

            E: adjacency list (all edge in E must be 0 or positive)

            start: start vertex

            INF: Infinity distance

        """

        self.G, self.INF = G, INF



    class Node:

        def __init__(self, v, cost):

            self.v, self.cost = v, cost



        def __lt__(self, n):

            return self.cost < n.cost



    def dijkstra(self, start, goal=None):

        que = list()

        self.dist = [self.INF] * self.G.V  # distance from start

        self.prev = [-1] * self.G.V  # prev vertex of shortest path

        self.dist[start] = 0

        heapq.heappush(que, (0, start))



        while len(que) > 0:

            cost, v = heapq.heappop(que)

            if self.dist[v] < cost:

                continue

            if goal is not None and v == goal:

                return

            for e in self.G.E[v]:

                if self.dist[v] + e.weight < self.dist[e.dst]:

                    self.dist[e.dst] = self.dist[v] + e.weight

                    heapq.heappush(que, (self.dist[e.dst], e.dst))

                    self.prev[e.dst] = v



    def getPath(self, end):

        path = [end]

        while self.prev[end] != -1:

            end = self.prev[end]

        return path[::-1]



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

G = Graph(V)

for _ in range(E):

    s, t, d = list(map(int, input().split()))

    G.add_edge(s, t, d)

INF = 10**9

sp = ShortestPath(G, INF)

sp.dijkstra(start)

for i in range(G.V):

    print(("INF" if sp.dist[i] == INF else sp.dist[i]))
from heapq import heapify, heappush, heappop

from collections import Counter, defaultdict, deque, OrderedDict

from sys import setrecursionlimit as setreclim

from sys import maxsize

from bisect import bisect_left, bisect, insort_left, insort

from math import ceil, log, factorial, hypot, pi

from fractions import gcd

from copy import deepcopy

from functools import reduce

from operator import mul

from itertools import product, permutations, combinations, accumulate, cycle

from string import ascii_uppercase, ascii_lowercase, ascii_letters, digits, hexdigits, octdigits

  

prod = lambda l: reduce(mul, l)

prodmod = lambda l, mod: reduce(lambda x, y: mul(x,y)%mod, l)

  

class Dijkstra:

    """Dijkstra's algorithm : find the shortest path from a vertex

       used in GRL1A(AOJ)

    """

  

    def __init__(self, V, E, start, INF=10**9):

        """ V: the number of vertexes

            E: adjacency list

            start: start vertex

            INF: Infinity distance

        """

        self.V = V

        self.E = E

        self.dijkstra(start, INF)

  

    def dijkstra(self, start, INF):

        que = list()

        self.distance = [INF] * self.V # distance from start

        self.distance[start] = 0

        heappush(que, (0, start))

  

        while len(que) > 0:

            dist, v = heappop(que)

            if self.distance[v] < dist: continue

            for to, cost in self.E[v]:

                if self.distance[v] + cost < self.distance[to]:

                    self.distance[to] = self.distance[v] + cost

                    heappush(que, (self.distance[to], to))

  

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

INF = 10**10

edge = [[] for _ in range(V)]

for i in range(E):

    s, t, cost = list(map(int, input().split()))

    edge[s].append((t, cost))

sp = Dijkstra(V, edge, r, INF)

for d in sp.distance:

    print((d if d != INF else 'INF'))
import heapq


class Edge:
    def __init__(self, dst, weight):
        self.dst, self.weight = dst, weight

    def __lt__(self, e):
        return self.weight > e.weight


class Graph:
    def __init__(self, V):
        self.V = V
        self.E = [[] for _ in range(V)]

    def add_edge(self, src, dst, weight):
        self.E[src].append(Edge(dst, weight))


class ShortestPath:
    """Dijkstra's algorithm : find the shortest path from a vertex
    Complexity: O(E + log(V))
    used in GRL1A(AOJ)
    """

    def __init__(self, G, INF=10**9):
        """V: the number of vertexes
        E: adjacency list (all edge in E must be 0 or positive)
        start: start vertex
        INF: Infinity distance
        """
        self.G, self.INF = G, INF

    class Node:
        def __init__(self, v, cost):
            self.v, self.cost = v, cost

        def __lt__(self, n):
            return self.cost < n.cost

    def dijkstra(self, start, goal=None):
        que = list()
        self.dist = [self.INF] * self.G.V  # distance from start
        self.prev = [-1] * self.G.V  # prev vertex of shortest path
        self.dist[start] = 0
        heapq.heappush(que, (0, start))
        while len(que) > 0:
            cost, v = heapq.heappop(que)
            if self.dist[v] < cost:
                continue
            if goal is not None and v == goal:
                return
            for e in self.G.E[v]:
                if self.dist[v] + e.weight < self.dist[e.dst]:
                    self.dist[e.dst] = self.dist[v] + e.weight
                    heapq.heappush(que, (self.dist[e.dst], e.dst))
                    self.prev[e.dst] = v

    def getPath(self, end):
        path = [end]
        while self.prev[end] != -1:
            end = self.prev[end]
        return path[::-1]


V, E, start = list(map(int, input().split()))
G = Graph(V)
for _ in range(E):
    s, t, d = list(map(int, input().split()))
    G.add_edge(s, t, d)
INF = 10**9
sp = ShortestPath(G, INF)
sp.dijkstra(start)
for i in range(G.V):
    print(("INF" if sp.dist[i] == INF else sp.dist[i]))

from heapq import heapify, heappush, heappop
from collections import Counter, defaultdict, deque, OrderedDict
from sys import setrecursionlimit as setreclim
from sys import maxsize
from bisect import bisect_left, bisect, insort_left, insort
from math import ceil, log, factorial, hypot, pi
from fractions import gcd
from copy import deepcopy
from functools import reduce
from operator import mul
from itertools import product, permutations, combinations, accumulate, cycle
from string import (
    ascii_uppercase,
    ascii_lowercase,
    ascii_letters,
    digits,
    hexdigits,
    octdigits,
)

prod = lambda l: reduce(mul, l)
prodmod = lambda l, mod: reduce(lambda x, y: mul(x, y) % mod, l)


class Dijkstra:
    """Dijkstra's algorithm : find the shortest path from a vertex
    used in GRL1A(AOJ)
    """

    def __init__(self, V, E, start, INF=10**9):
        """V: the number of vertexes
        E: adjacency list
        start: start vertex
        INF: Infinity distance
        """
        self.V = V
        self.E = E
        self.dijkstra(start, INF)

    def dijkstra(self, start, INF):
        que = list()
        self.distance = [INF] * self.V  # distance from start
        self.distance[start] = 0
        heappush(que, (0, start))
        while len(que) > 0:
            dist, v = heappop(que)
            if self.distance[v] < dist:
                continue
            for to, cost in self.E[v]:
                if self.distance[v] + cost < self.distance[to]:
                    self.distance[to] = self.distance[v] + cost
                    heappush(que, (self.distance[to], to))


V, E, r = list(map(int, input().split()))
INF = 10**10
edge = [[] for _ in range(V)]
for i in range(E):
    s, t, cost = list(map(int, input().split()))
    edge[s].append((t, cost))
sp = Dijkstra(V, edge, r, INF)
for d in sp.distance:
    print((d if d != INF else "INF"))

-import heapq +from heapq import heapify, heappush, heappop +from collections import Counter, defaultdict, deque, OrderedDict +from sys import setrecursionlimit as setreclim +from sys import maxsize +from bisect import bisect_left, bisect, insort_left, insort +from math import ceil, log, factorial, hypot, pi +from fractions import gcd +from copy import deepcopy +from functools import reduce +from operator import mul +from itertools import product, permutations, combinations, accumulate, cycle +from string import ( +    ascii_uppercase, +    ascii_lowercase, +    ascii_letters, +    digits, +    hexdigits, +    octdigits, +) + +prod = lambda l: reduce(mul, l) +prodmod = lambda l, mod: reduce(lambda x, y: mul(x, y) % mod, l) -class Edge: -    def __init__(self, dst, weight): -        self.dst, self.weight = dst, weight - -    def __lt__(self, e): -        return self.weight > e.weight - - -class Graph: -    def __init__(self, V): -        self.V = V -        self.E = [[] for _ in range(V)] - -    def add_edge(self, src, dst, weight): -        self.E[src].append(Edge(dst, weight)) - - -class ShortestPath: +class Dijkstra: -    Complexity: O(E + log(V)) -    def __init__(self, G, INF=10**9): +    def __init__(self, V, E, start, INF=10**9): -        E: adjacency list (all edge in E must be 0 or positive) +        E: adjacency list -        self.G, self.INF = G, INF +        self.V = V +        self.E = E +        self.dijkstra(start, INF) -    class Node: -        def __init__(self, v, cost): -            self.v, self.cost = v, cost - -        def __lt__(self, n): -            return self.cost < n.cost - -    def dijkstra(self, start, goal=None): +    def dijkstra(self, start, INF): -        self.dist = [self.INF] * self.G.V  # distance from start -        self.prev = [-1] * self.G.V  # prev vertex of shortest path -        self.dist[start] = 0 -        heapq.heappush(que, (0, start)) +        self.distance = [INF] * self.V  # distance from start +        self.distance[start] = 0 +        heappush(que, (0, start)) -            cost, v = heapq.heappop(que) -            if self.dist[v] < cost: +            dist, v = heappop(que) +            if self.distance[v] < dist: -            if goal is not None and v == goal: -                return -            for e in self.G.E[v]: -                if self.dist[v] + e.weight < self.dist[e.dst]: -                    self.dist[e.dst] = self.dist[v] + e.weight -                    heapq.heappush(que, (self.dist[e.dst], e.dst)) -                    self.prev[e.dst] = v - -    def getPath(self, end): -        path = [end] -        while self.prev[end] != -1: -            end = self.prev[end] -        return path[::-1] +            for to, cost in self.E[v]: +                if self.distance[v] + cost < self.distance[to]: +                    self.distance[to] = self.distance[v] + cost +                    heappush(que, (self.distance[to], to)) -V, E, start = list(map(int, input().split())) -G = Graph(V) -for _ in range(E): -    s, t, d = list(map(int, input().split())) -    G.add_edge(s, t, d) -INF = 10**9 -sp = ShortestPath(G, INF) -sp.dijkstra(start) -for i in range(G.V): -    print(("INF" if sp.dist[i] == INF else sp.dist[i])) +V, E, r = list(map(int, input().split())) +INF = 10**10 +edge = [[] for _ in range(V)] +for i in range(E): +    s, t, cost = list(map(int, input().split())) +    edge[s].append((t, cost)) +sp = Dijkstra(V, edge, r, INF) +for d in sp.distance: +    print((d if d != INF else "INF"))