h2. Date de intrare

Fisierul de intrare $dijkstra.in$ contine pe prima linie numerele $N$ si $M$, separate printr-un spatiu, cu semnificatia din enunt. Urmatoarele $M$ linii contin, fiecare, cate 3 numere naturale separate printr-un spatiu $A$ $B$ $C$ semnificand existenta unui arc de lungime $C$ de la nodul $A$ la nodul $B$.

Fisierul de intrare $dijkstra.in$ contine pe prima linie numerele $N$ si $M$, separate printr-un spatiu, cu semnificatia din enunt. Urmatoarele $M$ linii contin, fiecare, cate $3$ numere naturale separate printr-un spatiu $A$ $B$ $C$ semnificand existenta unui arc de lungime $C$ de la nodul $A$ la nodul $B$.

h2. Date de iesire

h2. Restrictii
* $1 ≤ N ≤ 100 000$

* Lungimile arcelor sunt numere naturale cel mult egale cu 1000.

* Lungimile arcelor sunt numere naturale cel mult egale cu $1 000$.

* Nu exista un arc de la un nod la acelasi nod.
* Daca nu exista drum de la nodul $1$ la un nod $i$, se considera ca lungimea minima este $0$.
* Arcele date in fisierul de intrare nu se repeta.

O rezolvare in O(N^2^) obtine 40 de puncte.
O rezolvare in O(NlogN) folosind un heap obtine 100 de puncte. O descriere a acestei structuri de date puteti gasi tot pe 'wikipedia':http://en.wikipedia.org/wiki/Binary_heap

...

h3. Probleme asemanatoare
 
* 'Distante':http://infoarena.ro/problema/distante
* 'Catun':http://infoarena.ro/problema/catun
 
!!!Problema nu este inca finalizata, s-ar putea sa se fi strecurat niste greseli in teste, mai trebuie sa fac niste verificari.

== include(page="template/taskfooter" task_id="dijkstra") ==