L = []
dist = []#lista de distante

for i in range(50003):#conform cerintei, putem avea cel mult 50000 noduri
    L.append([])#intial niciun nod nu are vecini

for i in range(50003):#conform cerintei, putem avea cel mult 50000 noduri
    dist.append(2000000000)#infinit

with open('dijkstra.in') as f:
    N, M = [int(x) for x in next(f).split()]#N = numarul de noduri, M = numarul de muchii
    array = []
    print("N, M = ", N, M)
    for line in f:  # read rest of lines
        linie = [int(x) for x in line.split()]
        if linie==[]:
            break
        x = linie[0]
        y = linie[1]#acum urmeaza sa trasam un arc de la x la y
        cost = linie[2]
        L[x].append((y, cost))#il adaug pe y la lista de vecini a lui x, cu costul c
        #daca aveam un graf neorientat, il adaugam si pe x in lista de vecini ai lui y

'''Pana acum am facut citirea clasica, care semana foarte mult cu cea de la BFS'''

'''Si in continuare va semana cu BFS-ul, cu cateva exceptii'''

'''La BFS foloseam o coada normala (acea structura de date comparabila cu o coada de la magazin, 
in sensul ca primul venit e primul "servit", iar cand un element nou vine in coada, se aseaza
in spatele cozii si va fi procesat abia dupa ce toate elementele din fata lui vor fi procesate)'''

'''La Dijkstra vom folosi o coada de prioritati. Adica o coada in care, la fiecare pas, nu procesez
elementul cel mai "vechi" din coada, ci elementul cel mai mic. (ca o coada "pe pile", in care
daca vine un element cu prioritatea foarte mare el se va aseza direct in fata cozii). In general
"prioritatea" inseamna ca elementul sa fie cat mai mic, dar in alte probleme prioritatea poate fi 
si ca elementul sa fie cat mai mare sau alte criterii.'''

import heapq#ne trebuie pentru a folosi coada de prioritati in Python

qq = []  # declar initial q ca o lista normala
print("type(q) = ", type(qq))
heapq.heapify(qq)  # asa transform din lista normala in coada de prioritati

heapq.heappush(qq,(4,10))
heapq.heappush(qq,(5,101))
heapq.heappush(qq,(-4,100))
heapq.heappush(qq,(40,0))
heapq.heappush(qq,(400,-1000))

print("q = ", qq)

print("N = ", N)

def Dijkstra(start):
    viz = [False] * 50003  # o metoda mai simpla de a initializa

    q = []  # declar initial q ca o lista normala
    print("type(q) = ", type(q))
    heapq.heapify(q)  # asa transform din lista normala in coada de prioritati
    print("type(q) = ", type(q))  # ramane tot list
    for i in range(50003):  # conform cerintei, putem avea cel mult 50000 noduri
        dist[i] = 2000000000
    dist[start] = 0
    heapq.heappush(q, (0, start))

    while q!=[]:
        x = q[0][1]#elementul din fata cozii (fara prioritatea lui)
        heapq.heappop(q)#il scoatem
        if viz[x]==False:
            viz[x] = True

            for i in range(len(L[x])):#parcurg vecinii lui x
                arc = L[x][i]
                y = arc[0]
                c = arc[1]
                if dist[y] > dist[x] + c:
                    dist[y] = dist[x] + c#relaxare
                    heapq.heappush(q, (dist[y], y))

Dijkstra(1)

for i in range(10):
    print("dist [", i, " = ", dist[i])

#acum afisam distantele calculate
rez = ""
for i in range(2, N+1):
    if dist[i]==2000000000:
        dist[i] = 0
    rez+=str(dist[i])
    if i!=N:
        rez+=" "
rez+="\n"
f = open("dijkstra.out", "w")
f.write(rez)
f.close()