dijkstra.py

num = int(input())
verteces = int(input())

data = [[-1]*(verteces+1) for i in range(verteces+1)]

for i in range(num):
    indata = [int(i) for i in input().split()]
    data[indata[0]][indata[1]] = indata[2]

current = 1
shortest = [-1]*(verteces+1)
shortest[1]=0
checked = [False]*(verteces+1)

while shortest[verteces]==-1:
    for id,i in enumerate(data[current]):
        if i!=-1:
            if shortest[id]==-1 or shortest[id]>shortest[current]+i:
                shortest[id] = shortest[current]+i
    checked[current] = True
    minval = 999999
    for i in range(verteces):
        if minval>shortest[i] and not checked[i] and shortest[i]!=-1:
            minval=shortest[i]
            vertex = i
    current=vertex

print(shortest)