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):

"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A&lang=jp

4.73[s]??§????????????AC
"""
from enum import Enum
from heapq import heappush, heappop


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


def solve(V, r, data):
    WHITE = 0
    GRAY = 1
    BLACK = 2
    num_of_nodes = V
    color = [WHITE] * num_of_nodes  
    d = [float('inf')] * num_of_nodes  
    adj = [[] for _ in range(num_of_nodes)]

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

    
    d[r] = 0
    pq = []
    heappush(pq, (0, r))

    while pq:
        cost, u = heappop(pq)
        color[u] = BLACK
        if d[u] < cost:
            continue

        for v, cost in adj[u]:
            if color[v] == BLACK:
                continue
            if d[v] > d[u] + cost:
                d[v] = d[u] + cost
                heappush(pq, (d[v], v))
                color[v] = GRAY

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


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

    
    solve(V, r, data)

Solution (Python):
from heapq import heappush, heappop
N, M, s = map(int, input().split())
Adj = [[] for i in range(N)]

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

d = [float("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

for di in d:
    print(di if di != float("inf") else 'INF')

Solution (Python):
from heapq import heappush, heappop
V, E, s = map(int, input().split())
Adj = [[] for i in range(V)]

for i in range(E):
    ui, vi, ci = map(int, input().split())
    Adj[ui].append([vi, ci])

d = [float("inf")] * V
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 == V - 1:
        break

for di in d:
    print(di if di != float("inf") else 'INF')

Solution (Python):
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

for j in range(v):
    update=False
    for i in range(v):
        for (t,d) in edge[i]:
            if dis[i]<inf and d<inf and dis[t]>dis[i]+d:
                dis[t]=dis[i]+d
                update=True
    if update==False: break

for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])

Solution (Python):
'''
????????£????????????????????????

'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))

while(not q.empty()):
    now=q.get()

    nowv=now[1]
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))


    
for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])

Solution (Python):
'''
????????£????????????????????????

'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))

'''
while(not q.empty()):
    now=q.get()

    nowv=now[1]
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
'''
finished=0
while(finished<v and not q.empty()):
    now=q.get()
    nowv=now[1]
    if now[0]>dis[nowv]: continue
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
    finished+=1       

for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])

Solution (Python):
'''
????????£????????????????????????

'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))


while(not q.empty()):
    now=q.get()
    nowv=now[1]
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
'''
finished=0
while(finished<v and not q.empty()):
    now=q.get()
    nowv=now[1]
    if now[0]>dis[nowv]: continue
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
    finished+=1       
'''
for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])

Solution (Python):
'''
????????£????????????1??????????????????
??\???C++??§????????????????§£?±???????????????????????????????????????§???
??????python??§??????????????????Accept??§??????????????????
????????£??¨optimization??????????????§??????
??§????????????Wrong Answer??§?????????
???????????????????????????????????????????????????
Online Judge???????????????Public Solutions??§????????????nanae?????????python3????????????????????????
????????£??¨?????????????????????
???????????????????????????0.06?§????????????§??????
'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))

'''
while(not q.empty()):
    now=q.get()
    nowv=now[1]
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
'''

finished=0
while(finished<v and not q.empty()):
    now=q.get()
    nowv=now[1]
    if now[0]>dis[nowv]: continue
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
    finished+=1       

for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])

Solution (Python):
'''
????????£????????????1??????????????????
??\???C++??§????????????????§£?±???????????????????????????????????????§???
??????python??§??????????????????Accept??§??????????????????
????????£??¨optimization??????????????§??????
??§????????????Wrong Answer??§?????????
???????????????????????????????????????????????????
Online Judge???????????????Public Solutions??§
????????????nanae?????????python3????????????????????????
????????£??¨?????????????????????
???????????????????????????0.06?§????????????§??????
'''

import queue
v,e,s=map(int,input().split())
edge=[]
inf =1000000100
for i in range(v):
    edge.append([])

for i in range(e):
    vs,vt,d=map(int,input().split())
    edge[vs].append((vt,d))
    
dis=[]
for i in range(v):
    dis.append(inf)

dis[s]=0

q = queue.PriorityQueue()
q.put((0,s))


while(not q.empty()):
    now=q.get()
    nowv=now[1]
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
'''

finished=0
while(finished<v and not q.empty()):
    now=q.get()
    nowv=now[1]
    if now[0]>dis[nowv]: continue
    for (vt,d) in edge[nowv]:
        if dis[vt]>dis[nowv]+d:
            dis[vt]=dis[nowv]+d
            q.put((dis[vt],vt))
    finished+=1       '''

for i in range(v):
    if dis[i]>=inf:
        print("INF")
    else:
        print(dis[i])

Solution (Python):
import time
import sys
start=time.clock()
def main():
    [V,E,r]=input().split(" ")
    V=int(V)
    E=int(E)
    r=int(r)
    edgeset=[]
    for i in range(E):
        [s,t,d]=input().split(" ")
        edgeset.append([int(s),int(t),int(d)])

    '''infile = open("GRL_1_A_in31.txt","r")
    data=[line.rstrip().split(' ') for line in infile]
    infile.close()
    V=int(data[0][0])
    E=int(data[0][1])
    r=int(data[0][2])
    edgeset=[[int(data[a][0]),int(data[a][1]),int(data[a][2])] for a in range(1,len(data))]'''

    
    '''read the edge information and put them to edgeset'''
    '''edgeset=binary_heap_sorting(edgeset)'''
    edgeset.sort()
    nedgeset=[[]]
    parameter=0
    for i in range(len(edgeset)):
        if(edgeset[i][0]!=parameter):
            for j in range(edgeset[i][0]-parameter):
                nedgeset.append([])
            parameter=edgeset[i][0]
            nedgeset[parameter].append(edgeset[i])
        else:
            nedgeset[parameter].append(edgeset[i])
    for i in range(V-len(nedgeset)):
        nedgeset.append([])
    edgeset=nedgeset

    setS=[]
    setV=[]
    setdist=[500000*10000+1 for i in range(V)]
    '''generate the sets for optimized vertices, unoptimized vertices, distance respectively'''

    setS.append(r)
    setV.append([r,0])
    setdist[r]=0
    '''initiating data'''

    for i in range(9999999999):
        nowvert=setS[-1]
        for j in range(len(edgeset[nowvert])):
            newdist=edgeset[nowvert][j][2]+setdist[nowvert]
            olddist=setdist[edgeset[nowvert][j][1]]
            '''calculating the new distance including the on process vertices'''
            if(newdist<olddist):
                setdist[edgeset[nowvert][j][1]]=newdist
                setV=binary_heap_add(setV,newdist,edgeset[nowvert][j][1])
            '''making comparision to determin which to stay'''
        if(setV==[[r,0]]):
            break
        setS.append(setV[1][0])
        setV=binary_heap_deletion(setV)
        '''find the next on process vertice'''
                    
    for i in range(V):
        if(setdist[i]==500000*10000+1):
            print('INF')
        else:
            print(setdist[i])
    '''data output'''
    
    return 0

def binary_heap_building(dataset):
    for i in [len(dataset)-x-1 for x in range(len(dataset))]:
        if(dataset[i][1]<dataset[int(i/2)][1]):
            trans=dataset[i]
            dataset[i]=dataset[int(i/2)]
            dataset[int(i/2)]=trans
    return dataset

def binary_heap_sorting(dataset):
    lenth=len(dataset)
    dataset.insert(0,[-1,-1])
    dataset=binary_heap_building(dataset)
    parameter=0
    ndataset=[[]]

    for i in range(lenth):
        if(parameter!=dataset[1][0]):
            for i in range(dataset[1][0]-parameter):
                ndataset.append([])
            parameter=dataset[1][0]
            ndataset[parameter].append(dataset[1])
        else:
            ndataset[parameter].append(dataset[1])
        dataset=binary_heap_deletion(dataset)
    print(1)
    return ndataset

    
def binary_heap_change(dataset,newdata,position):
    biposition=[a[0] for a in dataset].index(position)
    dataset[biposition][1]=newdata
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
            
        elif(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

    
    
def binary_heap_deletion(dataset):
    newdata=dataset[-1][1]
    trans=dataset[1]
    dataset[1]=dataset[-1]
    dataset[-1]=trans
    dataset.pop(-1)
    biposition=1
    for i in range(999999):
        if(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

def binary_heap_add(dataset,newdata,position):
    dataset.append([position,newdata])
    biposition=len(dataset)-1
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
        else:
            break
    return dataset

    
    
main()
'''elapsed = (time.clock() - start)
print("Time used:",elapsed)'''

Solution (Python):
import time
start=time.clock()
def main():
    [V,E,r]=input().split(" ")
    V=int(V)
    E=int(E)
    r=int(r)
    edgeset=[]
    for i in range(E):
        [s,t,d]=input().split(" ")
        edgeset.append([int(s),int(t),int(d)])
    '''read the edge information and put them to edgeset'''
    
    edgeset.sort()
    edgeset=reform(edgeset)

    setS=[]
    setV=[]
    setdist=[500000*10000+1 for i in range(V)]
    '''generate the sets for optimized vertices, unoptimized vertices, distance respectively'''

    setS.append(r)
    setV.append([r,0])
    setdist[r]=0
    '''initiating data'''

    for i in range(9999999999):
        nowvert=setS[-1]
        for j in range(len(edgeset[nowvert])):
            newdist=edgeset[nowvert][j][2]+setdist[nowvert]
            olddist=setdist[edgeset[nowvert][j][1]]
            '''calculating the new distance including the on process vertices'''
            if(newdist<olddist):
                setdist[edgeset[nowvert][j][1]]=newdist
                setV=binary_heap_add(setV,newdist,edgeset[nowvert][j][1])
            '''making comparision to determin which to stay'''
        if(setV==[[r,0]]):
            break
        setS.append(setV[1][0])
        setV=binary_heap_deletion(setV)
        '''find the next on process vertice'''
                    
    for i in range(V):
        if(setdist[i]==500000*10000+1):
            print('INF')
        else:
            print(setdist[i])
    '''data output'''
    
    return 0

def binary_heap_building(dataset):
    for i in [len(dataset)-x-1 for x in range(len(dataset))]:
        if(dataset[i][1]<dataset[int(i/2)][1]):
            trans=dataset[i]
            dataset[i]=dataset[int(i/2)]
            dataset[int(i/2)]=trans
    return dataset

def reform(dataset):
    lenth=len(dataset)
    parameter=0
    ndataset=[[]]

    for i in range(lenth):
        if(parameter!=dataset[i][0]):
            for j in range(dataset[i][0]-parameter):
                ndataset.append([])
            parameter=dataset[i][0]
            ndataset[parameter].append(dataset[i])
        else:
            ndataset[parameter].append(dataset[i])

    for i in range(lenth-parameter):
        ndataset.append([])
            
    return ndataset

    
def binary_heap_change(dataset,newdata,position):
    biposition=[a[0] for a in dataset].index(position)
    dataset[biposition][1]=newdata
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
            
        elif(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

    
    
def binary_heap_deletion(dataset):
    newdata=dataset[-1][1]
    trans=dataset[1]
    dataset[1]=dataset[-1]
    dataset[-1]=trans
    dataset.pop(-1)
    biposition=1
    for i in range(999999):
        if(biposition*2<len(dataset) and biposition*2+1<len(dataset) and (newdata>dataset[biposition*2][1] or newdata>dataset[biposition*2+1][1])):
            if(dataset[biposition*2][1]>=dataset[biposition*2+1][1]):
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2+1]
                dataset[biposition*2+1]=trans
                biposition=biposition*2+1
            else:
                trans=dataset[biposition]
                dataset[biposition]=dataset[biposition*2]
                dataset[biposition*2]=trans
                biposition=biposition*2
        else:
            break
    return dataset

def binary_heap_add(dataset,newdata,position):
    dataset.append([position,newdata])
    biposition=len(dataset)-1
    for i in range(999999):
        if(newdata<dataset[int(biposition/2)][1]):
            trans=dataset[biposition]
            dataset[biposition]=dataset[int(biposition/2)]
            dataset[int(biposition/2)]=trans
            biposition=int(biposition/2)
        else:
            break
    return dataset

    
    
main()
'''elapsed = (time.clock() - start)
print("Time used:",elapsed)'''

Solution (Python):



import sys
from collections import deque
import heapq
from collections import Counter
import math


class IN:
    @staticmethod
    def singleInt():
        return int(input())

    @staticmethod
    def singleStr():
        return input()

    @staticmethod
    def listInt():
        return list(map(int, input().split()))

    @staticmethod
    def listStr():
        return input().split()


print = lambda s: sys.stdout.write(str(s) + "\r\n")

def contain(c, x):
    return (x in c)

def str_reverse(s):
    return s[::-1]

def ctoi(c):
    return int.from_bytes(c.encode(), byteorder='big')
def itoc(x):
    return x.to_bytes((x.bit_length() + 7) // 8, byteorder='big').decode()

INF = 1001001001001001001
MOD = 1000000007


if __name__ == '__main__':
    N, M, S = IN.listInt()
    g = [[] for i in range(N)]
    for i in range(M):
        a, b, c = IN.listInt()
        g[a].append((b, c))
    
    hp = []
    dist = [INF for i in range(N)]
    heapq.heappush(hp, (0, S))
    dist[S] = 0
    while len(hp) > 0:
        _, v = heapq.heappop(hp)
        for (w, c) in g[v]:
            if dist[w] > dist[v] + c:
                dist[w] = dist[v] + c
                heapq.heappush(hp, (dist[w], w))

    for i in range(N):
        if dist[i] == INF:
            print("INF")
        else:
            print(dist[i])

Solution (Python):
import queue

def Dijkstra(vertex,edges,start):
	weight = [0 if i==start else float("inf") for i in range(vertex)]
	Q = queue.PriorityQueue()
	Q.put((weight[start],start))

	while(not Q.empty()):
		cur = Q.get()
		if weight[cur[1]] < cur[0]:
			continue
		for j in range(len(edges[cur[1]])):
			if weight[edges[cur[1]][j][1]] > weight[cur[1]] + edges[cur[1]][j][2]:
				weight[edges[cur[1]][j][1]] = weight[cur[1]] + edges[cur[1]][j][2]
				Q.put((weight[edges[cur[1]][j][1]],edges[cur[1]][j][1]))
	return weight

V,E,r = map(int,input().split())
edges = [[] for i in range(V)]
for i in range(E):
	data = list(map(int,input().split()))
	edges[data[0]].append(data)
for j in range(V):
	edges[j].sort()
w = Dijkstra(V,edges,r)
for i in range(len(w)):
	if w[i]==float("inf"):
		print('INF')
	else:
		print(w[i])

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



n_V, n_E, r = map(int, input().split())

E = [[] for _ in range(n_V)]
for i in range(n_E):
    v, e, c = map(int, input().split())
    E[v].append((e, c))



D = [sys.maxsize for _ in range(n_V)]
D[r] = 0

h = []
heappush(h, (D[r], r))



while len(h) != 0:
    _, index = heappop(h)

    for e, c in E[index]:
        d = D[index] + c
        if D[e] > d:
            D[e] = d
            heappush(h, (d, e))



for d in D:
    if d == sys.maxsize:
        print('INF')
    else:
        print(d)

Solution (Python):

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

g = [[] for i in range(v)] 

for i in range(e):
 s, t, d = map(int, input().split())
 g[s].append([t,d]) 


cost = ['INF' for i in range(v)] 
cost[r] = 0
finish = [] 
finish.append(r)

import heapq
h = []

u = r 

for count in range(v-1):

 for adj in g[u]:
  if cost[ adj[0] ] != 'INF':
   continue

  new_cost = cost[u] + adj[1]
  heapq.heappush(h, (new_cost, adj[0]))
  

 while 1:
  if len(h) == 0:
   break

  minc = heapq.heappop(h)
  if cost[ minc[1] ] == 'INF':
   cost[ minc[1] ] = minc[0]
   u = minc[1]
   break

for i in range(v):
 print(cost[i])

Solution (Python):

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

g = [[] for i in range(v)] 

for i in range(e):
 s, t, d = map(int, input().split())
 g[s].append([t,d]) 


cost = ['INF' for i in range(v)] 
cost[r] = 0

import heapq
h = []

u = r 

for count in range(v-1):

 for adj in g[u]:
  if cost[ adj[0] ] != 'INF':
   continue

  new_cost = cost[u] + adj[1]
  heapq.heappush(h, (new_cost, adj[0]))
  
  
 while 1:
  if len(h) == 0:
   break

  minc = heapq.heappop(h)
  if cost[ minc[1] ] == 'INF':
   cost[ minc[1] ] = minc[0]
   u = minc[1]
   break


for i in range(v):
 print(cost[i])

Solution (Python):

import heapq

[vertex, edge, r] = list(map(int, input("").split()))
infty = 999999999
final_c = [infty for i in range(vertex)]
dict_c = [[] for i in range(vertex)]

for i in range(edge):
    [e1, e2, c] = list(map(int, input("").split()))
    dict_c[e1].append((e2, c))

final_c[r] = 0
root_c = [(final_c[r], r)]

def Dijkstra(root, n):
    global infty, root_c, final_c, dict_c, root_c
    while(root_c):
        (cost, v) = heapq.heappop(root_c)
        if cost > final_c[v]:
            continue
        for i in range(len(dict_c[v])):
            (e2, c) = dict_c[v][i]
            if final_c[e2] > final_c[v] + c:
                final_c[e2] = final_c[v] + c
                heapq.heappush(root_c, (final_c[e2], e2))

Dijkstra(r, vertex)
for i in range(vertex):
    if final_c[i] == infty:
        print("INF")
    else:
        print(final_c[i])

Solution (Python):
import heapq

nv,ne,r = map(int, input().split())

nodes = [[] for _ in range(nv)]

for _ in range(ne):
    s,t,d = map(int, input().split())
    nodes[s].append((d, t))


costs = [-1] * nv
costs[r] = 0
hq = nodes[r]

while hq:
    cost, index = heapq.heappop(hq)
    if costs[index] > -1:
        continue
    costs[index] = cost
    for weight, next_index in nodes[index]:
        if costs[next_index] == -1:
            heapq.heappush(hq, (cost + weight, next_index))

for cost in costs:
    if cost == -1:
        print('INF')
        continue
    print(cost)

Solution (Python):
import queue


def dijkstra(n, graph, start):
    dist = [0 if i == start else float('inf') for i in range(n)]
    que = queue.PriorityQueue()
    que.put((0, start))

    while not que.empty():
        p = que.get()
        d, now = p[0], p[1]

        if dist[now] < d:
            continue

        for e in graph[now]:
            if dist[e[0]] <= d + e[1]:
                continue

            dist[e[0]] = dist[now] + e[1]
            que.put((dist[e[0]], e[0]))

    return dist


def main():
    n, m, s = map(int, input().split())
    graph = [[] for _ in range(n)]

    for _ in range(m):
        data = list(map(int, input().split()))

        graph[data[0]].append([data[1], data[2]])

    dist = dijkstra(n, graph, s)

    for d in dist:
        if d == float("inf"):
            print("INF")
        else:
            print(d)

    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def bellmanford(G,s):
    n = len(G)
    dist = [float("inf") for i in range(n)]
    dist[s]=0
    for k in range(n):
        flag = False
        for u in range(n):
            for v in range(len(G[u])):
                if dist[G[u][v][0]]>dist[u]+G[u][v][1]:
                    dist[G[u][v][0]]=dist[u]+G[u][v][1]
                    flag = True
        if(not flag):break
    for k in dist:
        if(k==float("inf")):print("INF")
        else:print(k)
                    
                        
def main():
    T =[int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    s = T[2]
    G = [[] for i in range(V)]
    
    for i in range(E):
        line = [int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append((line[1],line[2]))
    bellmanford(G,s)
main()

Solution (Python):
from heapq import heappop as pop
from heapq import heappush as push

INF = 10 ** 18

class edge:
  def __init__(self, to, cost):
    self.to = to
    self.cost = cost

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

G = [[] for i in range(V)]

d = [0 for i in range(V)]


def dijkstra(s, V):
  que = []
  global d
  global G
  d = [INF for i in range(V)]
  d[s] = 0
  push(que, (0,s))

  while len(que):
    p = pop(que)
    v = p[1]
    if (d[v] < p[0]):
      continue

    for i in range(len(G[v])):
      e = G[v][i]
      if d[e.to] > d[v] + e.cost:
        d[e.to] = d[v] + e.cost
        push(que, (d[e.to], e.to))

for i in range(E):
  s, t, c = map(int,input().split())
  G[s].append(edge(t,c))
dijkstra(r, V)

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

Solution (Python):
import sys
import heapq
def Dj(G,s):
    n = len(G)
    dist = [float("inf") for i in range(n)]
    vis = [-1 for i in range(n)]
    li = [(0,s)]
    dist[s]=0
    heapq.heapify(li)
    while len(li):
        d,u = heapq.heappop(li)
        if vis[u]==1:
            continue
        vis[u]=1
        for v in G[u]:
            if dist[v[1]]>dist[u] + v[0]:
                dist[v[1]] = dist[u] + v[0]
                heapq.heappush(li,(dist[u] + v[0],v[1]))
    return dist
                
    
    

def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    S = T[2]
    G = [[] for i in range(V)]
    for i in range(E):
        line = [int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append((line[2],line[1]))
    for k in Dj(G,S):
        if k ==float("inf"):print("INF")
        else:print(k)
main()

Solution (Python):
import sys
import heapq
def Dj(G,s):
    n = len(G)
    dist = [float("inf") for i in range(n)]
    vis = [-1 for i in range(n)]
    li = [(0,s)]
    dist[s]=0
    heapq.heapify(li)
    while len(li):
        d,u = heapq.heappop(li)
        if vis[u]==1:
            continue
        vis[u]=1
        for v in G[u]:
            if dist[v[1]]>dist[u] + v[0]:
                dist[v[1]] = dist[u] + v[0]
                heapq.heappush(li,(dist[u] + v[0],v[1]))
    return dist
                
    
    

def main():
    T = [int(x) for x in sys.stdin.readline().strip().split()]
    V = T[0]
    E = T[1]
    S = T[2]
    G = [[] for i in range(V)]
    for i in range(E):
        line = [int(x) for x in sys.stdin.readline().strip().split()]
        G[line[0]].append((line[2],line[1]))
    for k in Dj(G,S):
        if k ==float("inf"):print("INF")
        else:print(k)
main()