Problem:
Single Source Shortest Path For a given weighted graph G(V, E) and a source r , find the source shortest path to each vertex from the source (SSSP: Single Source Shortest Path). Input An edge-weighted graph G ( V , E ) and the source r . | V | | E | r  s 0  t 0  d 0  s 1  t 1  d 1 : s |E|-1  t |E|-1  d |E|-1   |V| is the number of vertices and |E| is the number of edges in G . The graph vertices are named with the numbers 0, 1,..., |V|-1 respectively. r is the source of the graph.  s i and t i represent source and target vertices of i -th edge (directed) and d i represents the cost of the i -th edge. Output Print the costs of SSSP in the following format.  c 0  c 1 : c |V|-1  The output consists of |V| lines. Print the cost of the shortest path from the source r to each vertex 0, 1, ... |V|-1 in order. If there is no path from the source to a vertex, print INF . Constraints  1 ≤ |V| ≤ 100000  0 ≤ d i ≤ 10000  0 ≤ |E| ≤ 500000  There are no parallel edges  There are no self-loops  Sample Input 1 4 5 0
0 1 1
0 2 4
1 2 2
2 3 1
1 3 5 Sample Output 1 0
1
3
4 Sample Input 2 4 6 1
0 1 1
0 2 4
2 0 1
1 2 2
3 1 1
3 2 5 Sample Output 2 3
0
2
INF

Solution (Python):
from collections import defaultdict

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

    
    d = {}
    INF = float('inf')
    
    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 d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop

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

    
    d = {}
    INF = float('inf')
    
    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 d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop

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

    
    d = {}
    INF = float('inf')
    
    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 d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from heapq import heappush, heappop

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

    
    d = {}
    INF = float('inf')
    
    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 d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict

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

    
    d = {}
    INF = float('inf')
    
    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 d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict

def main():
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    
    G = defaultdict(dict)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s][t] = w
    
    d = {}
    INF = float('inf')
    
    for i in range(V):
        d[i] = INF
    d[R] = 0
    q = [R]
    while q:
        u = q.pop(0)
        for v in 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()

Solution (Python):


from collections import defaultdict


def main():
    

    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t,w))
    
    d = {}
    INF = float('inf')
    
    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()

Solution (Python):
from collections import defaultdict
from collections import deque


def main():
    
    
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    
    G = defaultdict(list)
    for i in range(int(E)):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t, w))
    
    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])
    
    for k in range(V):
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])
    


if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
from collections import deque


def main():
    
    
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    
    G = defaultdict(dict)
    for i in range(E):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s][t] = w
    
    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].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()

Solution (Python):


'''
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


def main():
    
    
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    
    G = defaultdict(list)
    for i in range(E):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t, w))
    
    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])
    
    for k in d.keys():
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])
    


if __name__ == '__main__':
    main()

Solution (Python):


'''
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


def main():
    
    
    fl = input().split(" ")
    V = int(fl[0])
    E = int(fl[1])
    R = int(fl[2])
    
    G = defaultdict(list)
    for i in range(E):
        s, t, w = [int(x) for x in input().split(" ")]
        G[s].append((t, w))
    
    d = {}
    INF = float('inf')
    
    nodes_list = range(V)
    for i in nodes_list:
        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])
    for k in nodes_list:
        if d[k] == float('inf'):
            print("INF")
        else:
            print(d[k])
    
    


if __name__ == '__main__':
    main()

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
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].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])

Solution (Python):
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].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])

Solution (Python):
from collections import defaultdict
import heapq

vertice,edge,source = map(int,input().split(" "))
link = defaultdict(dict)
weight = defaultdict(dict)
answer = [-1] * vertice
for e in range(edge):
    i,j,w = map(int,input().split(" "))
    link[i] = link.get(i,set()) | {j}
    weight[i].update({j:w})
queue = []
heapq.heappush(queue,(0,source))
heapq.heapify(queue)
while queue:
    
    now_cost,here = heapq.heappop(queue)
    
    if answer[here] > -1:
        continue
    answer[here] = now_cost

    
    for nw in link[here]:
        if answer[nw] == -1:
            heapq.heappush(queue,(now_cost + weight[here][nw],nw))

for a in answer:
    print(a if a != -1 else "INF")

Solution (Python):
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 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])

Solution (Python):
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)
    
    while q:
        (cost, v) = heappop(q)
        if v not in d:
            
            d[v] = cost
            for (next, c) in 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])

Solution (Python):
from collections import defaultdict
from heapq import heappush, heappop, heapify
from sys import stdin


def sp(G,R,V):
    d = {}
    INF = float('inf')
    for i in range(V):
        d[i] = INF
    q = [(0, R)]
    d[R] = 0
    heapify(q)
    while q:
        (cost, v) = heappop(q)
        for (next, c) in G[v].items():
            if d[next] > d[v] + c:
                d[next] = d[v] + c
                heappush(q, (d[next], 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 d[k] == float('inf'):
            print("INF")
    else:
        print(d[k])

Solution (Python):
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([(0, R)])
    while q:
        (cost, v) = q.popleft()
        for (u, c) in G[v].items():
            if d[u] > d[v] + c:
                d[u] = d[v] + c
                q.append((d[u], u))
    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])

Solution (Python):
import sys
from heapq import heappush, heappop

inf = 1<<30

def solve():
    N, M, s = map(int, sys.stdin.readline().split())
    Adj = [[] for i in range(N)]

    for i in range(M):
        ui, vi, ci = map(int, sys.stdin.readline().split())
        Adj[ui].append((vi, ci))

    d = dijkstra(N, Adj, s)

    for di in d:
        print(di if di < inf else 'INF')

def dijkstra(N, Adj, s):
    d = [inf] * N
    p = [-1] * N
    fixed = [False] * N
    d[s] = 0
    p[s] = s
    pq = [(0, s)]

    for i in range(N - 1):
        while pq:
            di, v = heappop(pq)

            if not fixed[v] and di == d[v]:
                break

        fixed[v] = True

        for u, c in Adj[v]:
            if d[v] + c < d[u]:
                d[u] = d[v] + c
                p[u] = v
                heappush(pq, (d[u], u))

    return d

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
from heapq import heappush, heappop

inf = 1<<30

def solve():
    N, M, s = map(int, sys.stdin.readline().split())
    Adj = [[] for i in range(N)]

    for i in range(M):
        ui, vi, ci = map(int, sys.stdin.readline().split())
        Adj[ui].append((vi, ci))

    d = dijkstra(N, Adj, s)

    for di in d:
        print(di if di < inf else 'INF')

def dijkstra(N, Adj, s):
    d = [inf] * N
    d[s] = 0
    pq = [(0, s)]
    fixed = 0

    while pq:
        di, v = heappop(pq)

        if di > d[v]:
            continue

        for u, c in Adj[v]:
            if d[v] + c < d[u]:
                d[u] = d[v] + c
                heappush(pq, (d[u], u))

        fixed += 1

        if fixed == N - 1:
            break

    return d

if __name__ == '__main__':
    solve()

Solution (Python):
import heapq as pq
inf = float("inf")
n,e,r = map(int, input().split())
M = [[] for i in range(n)]

for i in range(e):
    s,t,d = map(int, input().split())
    M[s].append([t,d])
 
def dijkstra(s):
    color = [0] * n
    d = [inf] * n
    d[s] = 0
    H =[]
    pq.heappush(H, [0, s])
 
    while len(H) != 0:
        u2,u1 = pq.heappop(H)
        color[u1] = 1
        if d[u1] < u2:
            continue
        for v1,v2 in M[u1]:
            if color[v1] == 1: continue
            if d[u1] + v2 < d[v1]:
                d[v1] = d[u1] + v2
                pq.heappush(H, [d[v1], v1])
    return d
 
d = dijkstra(r)
for i in d:
 if i == inf: print("INF")
 else: print(i)

Solution (Python):
from heapq import heappush, heappop
V, E, r = map(int, input().split())
edges = [[] for _ in [None]*V]
vertices = [10**10]*V
vertices[r] = 0

for _ in [None]*E:
    s, t, d = 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]))

Solution (Python):
from heapq import heappush, heappop
V, E, r = 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 = 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]))

Solution (Python):
from heapq import heappush, heappop
V, E, r = 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 = 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]))

Solution (Python):
import sys
from heapq import heappush, heappop
readline = sys.stdin.readline
V, E, r = 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 = 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]))

Solution (Python):
from heapq import heappush, heappop
_input = input
V, E, r = 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 = map(int, _input().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]))

Solution (Python):
import heapq
import math


def main():
    nvertices, nedges, s = map(int, input().split())
    Adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        Adj[u].append((v, w))

    Q = [(0, s)]
    d = [float('inf')] * nvertices
    d[s] = 0
    while Q:
        w, u = heapq.heappop(Q)
        if d[u] < w:
            continue
        for v, cost in Adj[u]:
            if d[u] + cost < d[v]:
                d[v] = d[u] + cost
                heapq.heappush(Q, (d[v], v))

    for cost in d:
        if math.isinf(cost):
            print("INF")
        else:
            print(cost)


main()

Solution (Python):
import heapq
import math


def main():
    nvertices, nedges, s = map(int, input().split())
    edges = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        edges[u].append((v, w))
    INF = float('inf')
    hq = []
    for i in range(nvertices):
        heapq.heappush(hq, ((0 if i == s else INF), i))
    heapq.heapify(hq)
    weights = [INF] * nvertices
    weights[s] = 0
    while hq:
        d, u = heapq.heappop(hq)
        if d > weights[u]:
            continue
        for v, w in edges[u]:
            if weights[u] + w < weights[v]:
                weights[v] = weights[u] + w
                heapq.heappush(hq, (weights[v], v))

    for w in weights:
        print("INF" if math.isinf(w) else w)


main()

Solution (Python):
import heapq
import math


def main():
    nvertices, nedges, s = map(int, input().split())
    edges = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        edges[u].append((v, w))
    INF = float('inf')
    hq = [(0, s)]
    weights = [INF] * nvertices
    weights[s] = 0
    while hq:
        d, u = heapq.heappop(hq)
        if d > weights[u]:
            continue
        for v, w in edges[u]:
            if weights[u] + w < weights[v]:
                weights[v] = weights[u] + w
                heapq.heappush(hq, (weights[v], v))

    for w in weights:
        print("INF" if math.isinf(w) else w)


main()

Solution (Python):
from collections import defaultdict

INF = 999999999999999999999

def dijkstra(G, s):
  heap = Heap()
  heap.push((s, 0))
  fixed = set()
  d = defaultdict(lambda: INF)
  d[s] = 0
  while len(heap.data) > 0:
    v = heap.pop()
    if v in fixed:
      continue
    for u in G[v]:
      if u in fixed:
        continue
      c = G[v][u]
      if d[v] + c < d[u]:
        d[u] = d[v] + c
        heap.push((u, d[u]))
    fixed.add(v)
  return d


class Heap:
  def __init__(self):
    self.data = []

  def push(self,x):
    self.data.append(x)
    i = len(self.data)-1
    while self._p(i) >= 0:
      if self.data[i][1] < self.data[self._p(i)][1]:
        tmp = self.data[i]
        self.data[i] = self.data[self._p(i)]
        self.data[self._p(i)] = tmp
        i = self._p(i)
      else:
        break

  def pop(self):
    ret = self.top()
    n = self.data.pop()
    if len(self.data) > 0:
      self.data[0] = n
      i = 0
      while True:
        if self._l(i) < len(self.data):
          l = self.data[self._l(i)]
        else:
          l = (-1, INF)
        if self._r(i) < len(self.data):
          r = self.data[self._r(i)]
        else:
          r = (-1, INF)
        if l[1] > r[1]:
          if r[1] < self.data[i][1]:
            tmp = self.data[i]
            self.data[i] = self.data[self._r(i)]
            self.data[self._r(i)] = tmp
            i = self._r(i)
          else:
            break
        else:
          if l[1] < self.data[i][1]:
            tmp = self.data[i]
            self.data[i] = self.data[self._l(i)]
            self.data[self._l(i)] = tmp
            i = self._l(i)
          else:
            break
    return ret[0]

  def top(self):
    return self.data[0]

  def _p(self, i):
    i = i+1
    return i//2-1

  def _l(self, i):
    i = i+1
    return i*2-1

  def _r(self, i):
    i = i+1
    return i*2


G = {}

n, m, r = [int(v) for v in input().strip().split(' ')]
for i in range(n):
  G[i] = {}
for _ in range(m):
  s, t, c = [int(v) for v in input().strip().split(' ')]
  G[s][t] = c

d = dijkstra(G, r)

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

Solution (Python):
import heapq


def main():
    nvertices, nedges, s = map(int, input().split())
    adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))

    INF = float('inf')
    costs = [INF] * nvertices
    que = [(0, s)]
    for i in range(1, nvertices):
        que.append((INF, 1))
    while que:
        cost, u = heapq.heappop(que)
        if cost > costs[u]:
            continue
        costs[u] = cost
        for v, w in adj[u]:
            if costs[v] > costs[u] + w:
                costs[v] = costs[u] + w
                heapq.heappush(que, (costs[v], v))

    for i in range(nvertices):
        print(costs[i] if costs[i] < INF else "INF")


main()

Solution (Python):
import heapq


def main():
    nvertices, nedges, s = map(int, input().split())
    adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))

    INF = float('inf')
    costs = [INF] * nvertices
    costs[s] = 0
    que = [(0, s)]
    for i in range(1, nvertices):
        que.append((INF, 1))
    while que:
        cost, u = heapq.heappop(que)
        if cost > costs[u]:
            continue
        costs[u] = cost
        for v, w in adj[u]:
            if costs[v] > costs[u] + w:
                costs[v] = costs[u] + w
                heapq.heappush(que, (costs[v], v))

    for i in range(nvertices):
        print(costs[i] if costs[i] < INF else "INF")


main()

Solution (Python):
import heapq


def main():
    nvertices, nedges, s = map(int, input().split())
    adj = [[] for i in range(nvertices)]
    for i in range(nedges):
        u, v, w = map(int, input().split())
        adj[u].append((v, w))

    INF = float('inf')
    costs = [INF] * nvertices
    costs[s] = 0
    que = [(0, s)]
    for i in range(1, nvertices):
        que.append((INF, 1))
    cnt = 0
    while que:
        cost, u = heapq.heappop(que)
        if cost > costs[u]:
            continue
        costs[u] = cost
        for v, w in adj[u]:
            if costs[v] > costs[u] + w:
                costs[v] = costs[u] + w
                heapq.heappush(que, (costs[v], v))
        cnt += 1
        if cnt == nvertices:
            break

    for i in range(nvertices):
        print(costs[i] if costs[i] < INF else "INF")


main()

Solution (Python):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp
"""
from enum import Enum
from heapq import heappush, heappop, heapify

class Sssp(object):
    """ single source shortest path """
    class Status(Enum):
        """ ?????????????¨??????¶??? """
        white = 1  
        gray = 2  
        black = 3  

    def __init__(self, V, data):
        num_of_nodes = V
        self.color = [Sssp.Status.white] * num_of_nodes  
        self.d = [float('inf')] * num_of_nodes  
        self.p = [-1] * num_of_nodes  
        self.adj = [[] for _ in range(num_of_nodes)]
        self.make_adj(data)


    def make_adj(self, data):
        
        for f, t, c in data:
            self.adj[f].insert(0, (t, c))
            

    def dijkstra(self, start):
        self.d[start] = 0
        pq = []
        heappush(pq, (0, start))

        while pq:
            cost, u = heappop(pq)
            self.color[u] = Sssp.Status.black
            if self.d[u] < cost:
                continue

            for v, cost in self.adj[u]:
                if self.color[v] == Sssp.Status.black:
                    continue
                if self.d[v] > self.d[u] + cost:
                    self.d[v] = self.d[u] + cost
                    heappush(pq, (self.d[v], v))
                    self.color[v] = Sssp.Status.gray



if __name__ == '__main__':
    
    V, E, r = [int(x) for x in input().split(' ')]
    data = []
    for i in range(E):
        data.append(list(map(int, input().split(' '))))

    
    s = Sssp(V, data)
    s.dijkstra(r)

    
    for i in range(V):
        if s.d[i] == float('inf'):
            print('INF')
        else:
            print('{}'.format(s.d[i]))