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

Measured memory_bytes: 147424