Cerința

Se dă un graf orientat ponderat cu n noduri – în care fiecare arc are asociat un cost, număr natural strict pozitiv, și un nod p. Să se determine, folosind algoritmul lui Dijkstra, costul minim al drumului de la p la fiecare nod al grafului.

Date de intrare

Fișierul de intrare dijkstra.in conține pe prima linie numerele n p, iar următoarele linii câte un triplet i j c, cu semnificația: există arcul (i j) și are costul c.

Date de ieșire

Fișierul de ieșire dijkstra.out va conține pe prima linie n numere, separate prin exact un spațiu, al i-lea număr reprezentând costul drumului minim de la p la i. Dacă nu există drum de la p la un anumit vârf, costul afișat va fi -1.

Restricții și precizări

• 1 ≤ n ≤ 100
• costul unui arc va fi mai mic decât 1000
• costul unui drum este egal cu suma costurilor arcelor care îl compun

Exemplu:

dijkstra.in

5 4
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2

dijkstra.out

3 1 4 0 -1