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 = map(int, input().split())
INF = 10**10
edge = [[] for _ in range(V)]
for i in range(E):
????????s, t, cost = 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')

### FIXED CODE ###

import heapq
from typing import List, TypeVar, Generic
T = TypeVar('T', int, float)


class Edge(Generic[T]):
    def __init__(self, dst: int, weight: T) -> None:
        self.dst: int = dst
        self.weight: T = weight

    def __lt__(self, e: 'Edge') -> bool:
        return self.weight > e.weight


class Graph(Generic[T]):
    def __init__(self, V: int) -> None:
        self.V: int = V
        self.E: List[List[Edge[T]]] = [[] for _ in range(V)]

    def add_edge(self, src: int, dst: int, weight: T) -> None:
        self.E[src].append(Edge(dst, weight))


class Node(Generic[T]):
    def __init__(self, v: int, cost: T) -> None:
        self.v: int = v
        self.cost: T = cost

    def __lt__(self, n: 'Node') -> bool:
        return self.cost < n.cost


class ShortestPath(Generic[T]):
    def __init__(self, G: Graph[T], inf: T = 10**9) -> None:
        self.G: Graph[T] = G
        self.inf: T = inf
        self.dist: List[T] = [self.inf] * self.G.V  # distance from start
        self.prev: List[int] = [-1] * self.G.V  # prev vertex of shortest path

    def run(self, start: int, goal: int = -1) -> None:
        que: List[Node] = list()
        self.dist[start] = 0
        heapq.heappush(que, Node[T](start, 0))

        while que:
            node: Node[T] = heapq.heappop(que)
            if self.dist[node.v] < node.cost:
                continue
            if goal != -1 and node.v == goal:
                return
            for edge in self.G.E[node.v]:
                if self.dist[node.v] + edge.weight < self.dist[edge.dst]:
                    self.dist[edge.dst] = self.dist[node.v] + edge.weight
                    heapq.heappush(que, Node(edge.dst, self.dist[edge.dst]))
                    self.prev[edge.dst] = node.v

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

def main() -> None:
    V, E, start = map(int, input().split())
    graph = Graph[int](V)
    for _ in range(E):
        s, t, d = map(int, input().split())
        graph.add_edge(s, t, d)
    inf = int(1e10)
    sp = ShortestPath[int](graph, inf)
    sp.run(start)
    for i in range(V):
        print(sp.dist[i] if sp.dist[i] != inf else "INF")

if __name__ == '__main__':
    main()