CodeEff/ECCO huggingface dataset:
# Original solution
import sys
import queue


class Dijkstra:
    class Edge:
        def __init__(self, end, cost):
            self.to = end
            self.cost = cost

    def __init__(self, node_size, inf):
        self._node = node_size
        self._graph = [[] for _ in range(self._node)]
        self.inf = inf
        self.dist = [self.inf for _ in range(self._node)]

    def add_edge(self, st, ed, cs):
        self._graph[st].append(self.Edge(ed, cs))

    def solve(self, start):
        que = queue.PriorityQueue()
        self.dist[start] = 0
        que.put((0, start))
        while not que.empty():
            cur_cost, cur_vertex = que.get()
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if self.dist[e.to] > cur_cost + e.cost:
                    self.dist[e.to] = cur_cost + e.cost
                    que.put((self.dist[e.to], e.to))


if __name__ == '__main__':
    V, E, r = list(map(int, sys.stdin.readline().split()))
    dk = Dijkstra(V, 10 ** 10)
    for i in range(E):
        s, t, d = list(map(int, sys.stdin.readline().split()))
        dk.add_edge(s, t, d)
    dk.solve(r)
    for value in dk.dist:
        if value == dk.inf:
            print("INF")
        else:
            print(value)


# Optimized solution
import sys
from heapq import heappush, heappop


class Dijkstra:
    class Edge:
        def __init__(self, end, cost):
            self.to = end
            self.cost = cost

    def __init__(self, node_size, inf):
        self._node = node_size
        self._graph = [[] for _ in range(self._node)]
        self.inf = inf
        self.dist = [self.inf for _ in range(self._node)]

    def add_edge(self, st, ed, cs):
        self._graph[st].append(self.Edge(ed, cs))

    def solve(self, start):
        que = []
        self.dist[start] = 0
        heappush(que, (0, start))
        while que:
            cur_cost, cur_vertex = heappop(que)
            if self.dist[cur_vertex] < cur_cost:
                continue
            for e in self._graph[cur_vertex]:
                if self.dist[e.to] > cur_cost + e.cost:
                    self.dist[e.to] = cur_cost + e.cost
                    heappush(que, (self.dist[e.to], e.to))


if __name__ == '__main__':
    V, E, r = list(map(int, sys.stdin.readline().split()))
    dk = Dijkstra(V, 10 ** 10)
    for i in range(E):
        s, t, d = list(map(int, sys.stdin.readline().split()))
        dk.add_edge(s, t, d)
    dk.solve(r)
    for value in dk.dist:
        if value == dk.inf:
            sys.stdout.write("INF\n")
        else:
            sys.stdout.write("%s\n" % value)
# Original solution
import sys
import heapq


def dfs(u,s,target, vs):
    vs[u] = 1
    if(u == target):
        global h
        heapq.heappush(h,s)
        return
    for j in range(e):
        if(e_1[j] == u):
            if(vs[e_2[j]] != 1):
                count = s + e_w[j]
                print((s,e_2[j],vs))
                dfs(e_2[j],count,target,vs[0:])



v,e,r=list(map(int, input().split()));

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = list(map(int, input().split()));

v_q=[];

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
heapq.heappush(v_q,(0,r))
while(len(v_q) != 0):
    cost,u = heapq.heappop(v_q)
    if(cost > d[u]):
        continue
    for j in range(e):
        if(u == e_1[j]):
            alt = cost+e_w[j]
            if(d[e_2[j]] > alt):
                d[e_2[j]] = alt
                heapq.heappush(v_q,(alt,e_2[j]))

for i in range(v):
    if(d[i] != INF):
        print((d[i]))
    else:
        print("INF")





# Optimized solution
import sys
import heapq

v,e,r=list(map(int, input().split()));

e_1=[0]*e;
e_2=[0]*e;
e_w=[0]*e;

for i in range(e):
    e_1[i], e_2[i], e_w[i] = list(map(int, input().split()));

v_q=[];

INF = 9999999999999999999
d = [INF for i in range(v)]
d[r] = 0
heapq.heappush(v_q,(0,r))
while(len(v_q) != 0):
    cost,u = heapq.heappop(v_q)
    if(cost > d[u]):
        continue
    for j in range(e):
        if(u == e_1[j]):
            alt = cost+e_w[j]
            if(d[e_2[j]] > alt):
                d[e_2[j]] = alt
                heapq.heappush(v_q,(alt,e_2[j]))

for i in range(v):
    if(d[i] != INF):
        print((d[i]))
    else:
        print("INF")
# Original solution
from heapq import heappush, heappop
V, E, r = list(map(int, input().split()))
edges = [[] for _ in [None]*V]
vertices = [10**10]*V
vertices[r] = 0

for _ in [None]*E:
    s, t, d = list(map(int, input().split()))
    edges[s].append((t,d))

q = [(0, r)]
while q:
    cost, v = heappop(q)
    for dest, _cost in edges[v]:
        newcost = cost + _cost
        if vertices[dest] > newcost:
            vertices[dest] = newcost
            heappush(q, (newcost, dest))

print(("\n".join([str(n) if n!=10**10 else "INF" for n in vertices])))

# Optimized solution
from heapq import heappush, heappop
V, E, r = list(map(int, input().split()))
inf = 10**10
edges = [[] for _ in [None]*V]
vertices = [inf]*V
vertices[r] = 0

for _ in [None]*E:
    s, t, d = list(map(int, input().split()))
    edges[s].append((t, d))

q = [(0, r)]
rem = V-1
while q and rem > 0:
    cost, v = heappop(q)
    if vertices[v] < cost:
        continue
    rem -= 1
    for dest, _cost in edges[v]:
        newcost = cost + _cost
        if vertices[dest] > newcost:
            vertices[dest] = newcost
            heappush(q, (newcost, dest))

print(("\n".join([str(n) if n!=inf else "INF" for n in vertices])))
# Original solution
from heapq import heappush, heappop
V, E, r = list(map(int, input().split()))
inf = 10**10
edges = [[] for _ in [None]*V]
vertices = [inf]*V
vertices[r] = 0

for _ in [None]*E:
    s, t, d = list(map(int, input().split()))
    edges[s].append((t, d))

q = [(0, r)]
rem = V-1
while q:
    cost, v = heappop(q)
    if vertices[v] < cost:
        continue
    for dest, _cost in edges[v]:
        newcost = cost + _cost
        if vertices[dest] > newcost:
            vertices[dest] = newcost
            heappush(q, (newcost, dest))
    rem -= 1
    if rem == 0:
        break

print(("\n".join([str(n) if n!=inf else "INF" for n in vertices])))

# Optimized solution
import sys
from heapq import heappush, heappop
readline = sys.stdin.readline
V, E, r = list(map(int, readline().split()))
inf = 10**10
edges = [[] for _ in [None]*V]
vertices = [inf]*V
vertices[r] = 0

for _ in [None]*E:
    s, t, d = list(map(int, readline().split()))
    edges[s].append((t, d))

q = [(0, r)]
rem = V-1
while q and rem:
    cost, v = heappop(q)
    if vertices[v] < cost:
        continue
    rem -= 1
    for dest, _cost in edges[v]:
        newcost = cost + _cost
        if vertices[dest] > newcost:
            vertices[dest] = newcost
            heappush(q, (newcost, dest))

print(("\n".join([str(n) if n!=inf else "INF" for n in vertices])))
# Original solution
from heapq import heappush, heappop
V, E, r = list(map(int, input().split()))
g = [[] for i in range(V)]
for i in range(E):
    s, t, d = list(map(int, input().split()))
    g[s].append((t, d))

INF = 10**10
dist = [INF]*V
que = [(0,r)]
dist[r] = 0
while que:
    c, v = heappop(que)
    if dist[v] < c:
        continue
    for t, cost in g[v]:
        if dist[v] + cost < dist[t]:
            dist[t] = dist[v] + cost
            heappush(que, (dist[t], t))
for i in range(V):
    print(dist[i] if dist[i]<INF else "INF")

# Optimized solution
class RadixHeap:
    __slots__ = ["data", "last", "siz", "used"]

    # (max_key - min_key) <= C
    def __init__(self, N, C):
        self.data = [[] for i in range(C.bit_length() + 1)]
        self.last = self.siz = 0
        self.used = [0]*N

    def push(self, x, key):
        #assert self.last <= x
        self.siz += 1
        self.data[(x ^ self.last).bit_length()].append((x, key))

    def pop(self):
        data = self.data
        used = self.used
        #assert self.siz > 0
        if not data[0]:
            i = 1
            while not data[i]:
                i += 1
            d = data[i]
            new_last, new_key = min(d)
            used[new_key] = 1
            for val in d:
                x, key = val
                if used[key]:
                    self.siz -= 1
                    continue
                data[(x ^ new_last).bit_length()].append(val)
            self.last = new_last
            data[i] = []
        else:
            new_last, new_key = data[0].pop()
            used[new_key] = 1
            self.siz -= 1
        return new_last, new_key

    def __len__(self):
        return self.siz

import sys
readline = sys.stdin.readline
write = sys.stdout.write

N, M, s = list(map(int, readline().split()))
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = list(map(int, readline().split()))
    G[a].append((b, c))

INF = 10**18
def dijkstra(N, G, s):
    que = RadixHeap(N, 10**9 + 1)

    dist = [INF]*N
    dist[s] = 0
    que.push(0, s)
    while que:
        cost, v = que.pop()
        if dist[v] < cost:
            continue
        for w, c in G[v]:
            if cost + c < dist[w]:
                dist[w] = r = cost + c
                que.push(r, w)
    return dist

dist = dijkstra(N, G, s)
for c in dist:
    write("INF\n" if c == INF else "%d\n" % c)
# Original solution

from collections import defaultdict
from heapq import heappush, heappop

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = heappop(q)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                heappush(q, v[0])

    for k in list(d.keys()):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))

if __name__ == '__main__':
    main()

# Optimized solution

from collections import defaultdict
from heapq import heappush, heappop

def main():
    #Read stdin
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))

    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        #u = heappop(q)
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                #heappush(q, v[0])
                q.append(v[0])


    for k in list(d.keys()):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))

if __name__ == '__main__':
    main()
# Original solution
#!usr/bin/env python3
from collections import defaultdict

def main():
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(dict)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s][t] = w
    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in list(G[u].keys()):
            if d[v] > d[u] + G[u][v]:
                d[v] = d[u] + G[u][v]
                q.append(v)

    for k in range(V):
        if d[k] == float('inf'):
            
            print("INF")
        else:
            print((d[k]))



if __name__ == '__main__':
    main()

# Optimized solution
#!usr/bin/env python3

from collections import defaultdict


def main():
    #Read stdin

    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))
    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]

                q.append(v[0])

    for k in range(V):
        if d[k] == float('inf'):
            
            print("INF")
        else:
            print((d[k]))



if __name__ == '__main__':
    main()
# Original solution
#!usr/bin/env python3

from collections import defaultdict


def main():
    #Read stdin

    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    #Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))
    #initialized
    d = {}
    INF = float('inf')
    #INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]

                q.append(v[0])

    for k in range(V):
        if d[k] == float('inf'):
            
            print("INF")
        else:
            print((d[k]))



if __name__ == '__main__':
    main()

# Optimized solution
from collections import defaultdict
from collections import deque
#import time

def main():
    # Read stdin
    #start = time.clock()
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    # Adjacency list
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t, w))
    # initialized
    d = {}
    INF = float('inf')
    # INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([R])
    while q:
        # u = heappop(q)
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                # heappush(q, v[0])
                q.append(v[0])
    #end = time.clock() - start
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))
    #print('Computation time : {}'.format(end))


if __name__ == '__main__':
    main()
# Original solution

from collections import defaultdict
from collections import deque
#import time

def main():
    # Read stdin
    #start = time.clock()
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    # Adjacency list
    G = defaultdict(dict)
    for i in range(E):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s][t] = w
    # initialized
    d = {}
    INF = float('inf')
    # INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    # deque is better than list aka double link list O(1) for pop head and append
    q = deque([R])
    while q:
        # u = heappop(q)
        u = q.popleft()
        for v in list(G[u].keys()):
            if d[v] > d[u] + G[u][v]:
                d[v] = d[u] + G[u][v]
                # heappush(q, v[0])
                q.append(v)
    #end = time.clock() - start
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))
    #print('Computation time : {}'.format(end))


if __name__ == '__main__':
    main()

# Optimized solution
#!usr/bin/env python3

'''
time score 7.88 for list
time score 03.17 for deque
time score 03.22 for defaultdict(dict)

''' 

from collections import defaultdict
from collections import deque
#import time

def main():
    # Read stdin
    #start = time.clock()
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    # Adjacency list
    G = defaultdict(list)
    for i in range(E):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t, w))
    # initialized
    d = {}
    INF = float('inf')
    # INF = 10001
    for i in range(V):
        d[i] = INF
    d[R] = 0
    # deque is better than list aka double link list O(1) for pop head and append
    q = deque([R])
    while q:
        # u = heappop(q)
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                # heappush(q, v[0])
                q.append(v[0])
    #end = time.clock() - start
    for k in list(d.keys()):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))
    #print('Computation time : {}'.format(end))


if __name__ == '__main__':
    main()
# Original solution
#!usr/bin/env python3

'''
time score 7.88 for list
time score 03.17 for deque
time score 03.22 for defaultdict(dict)

''' 

from collections import defaultdict
from collections import deque
#import time

def main():
    # Read stdin
    #start = time.clock()
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    # Adjacency list
    G = defaultdict(list)
    for i in range(E):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t, w))
    # initialized
    d = {}
    INF = float('inf')
    # INF = 10001
    nodes_list = list(range(V))
    for i in nodes_list:
        d[i] = INF
    d[R] = 0
    # deque is better than list aka double link list O(1) for pop head and append
    q = deque([R])
    while q:
        # u = heappop(q)
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                # heappush(q, v[0])
                q.append(v[0])
    for k in nodes_list:
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))
    #end = time.clock() - start
    #print('Computation time : {}'.format(end))


if __name__ == '__main__':
    main()

# Optimized solution
from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([(R)])
    while q:
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])
    return d


V, E, R = tuple(int(x) for x in stdin.readline().split(' '))
G = defaultdict(list)
for case in range(E):
    s, t, w = tuple(int(x) for x in stdin.readline().split(' '))
    G[s].append((t,w))
d = sp(G, R, V)
for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))
# Original solution
from collections import defaultdict
from collections import deque
from sys import stdin


def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([(R)])
    while q:
        u = q.popleft()
        for v in G[u]:
            if d[v[0]] > d[u] + v[1]:
                d[v[0]] = d[u] + v[1]
                q.append(v[0])
    return d


V, E, R = [int(x) for x in stdin.readline().split(' ')]
G = defaultdict(list)
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split(' ')]
    G[s].append((t,w))
d = sp(G, R, V)
for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))

# Optimized solution
from collections import defaultdict
from collections import deque
from sys import stdin


def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([(R)])
    while q:
        u = q.popleft()
        for v in list(G[u].keys()):
            if d[v] > d[u] + G[u][v]:
                d[v] = d[u] + G[u][v]
                q.append(v)
    return d


V, E, R = [int(x) for x in stdin.readline().split(' ')]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split(' ')]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))
# Original solution
from collections import defaultdict
from collections import deque
from sys import stdin


def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([(R)])
    while q:
        u = q.popleft()
        for v in list(G[u].keys()):
            if d[v] > d[u] + G[u][v]:
                d[v] = d[u] + G[u][v]
                q.append(v)
    return d


V, E, R = [int(x) for x in stdin.readline().split(' ')]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split(' ')]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))

# Optimized solution
from collections import defaultdict
from collections import deque
from sys import stdin

def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = deque([(R)])
    while q:
        u = q.popleft()
        for v in list(G[u].keys()):
            if d[v] > d[u] + G[u][v]:
                d[v] = d[u] + G[u][v]
                q.append(v)
    return d


V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print((d[k]))
# Original solution
from collections import defaultdict
from heapq import heappush, heappop, heapify
from sys import stdin
def sp(G,R,V):
    d = {}
    q = [(0, R)]
    heapify(q)
    seen = set()
    while q:
        (cost, v) = heappop(q)
        if v not in seen:
            seen.add(v)
            d[v] = cost
            for (next, c) in list(G[v].items()):
                heappush(q, (cost + c, next))
    return d

V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin.readline().split()]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
    if k not in d:
        print("INF")
    else:
        print((d[k]))

# Optimized solution
from collections import defaultdict
from heapq import heappush, heappop, heapify
from sys import stdin
def sp(G,R,V):
    d = {}
    q = [(0, R)]
    heapify(q)
    #seen = set()
    while q:
        (cost, v) = heappop(q)
        if v not in d:
            #seen.add(v)
            d[v] = cost
            for (next, c) in list(G[v].items()):
                heappush(q, (cost + c, next))
    return d

V, E, R = [int(x) for x in stdin.readline().split()]
G = defaultdict(dict)
for case in range(E):
    s, t, w = [int(x) for x in stdin
    .readline().split()]
    G[s][t] = w
d = sp(G, R, V)
for k in range(V):
    if k not in d:
        print("INF")
    else:
        print((d[k]))