Un elf dorește să știe care este distanța
minimă dintre satul său natal și fiecare
dintre cele n sate ale elfilor.
El are o hartă pe care sunt specificate lungimile cărărilor care leagă satele elfilor. Satele elfilor sunt identificate prin numere cuprinse între 1 și n, iar satul natal al elfului curios este identificat prin 1.
Fișierul de intrare INPUT.TXT conține
pe prima linie numărul n al satelor
elfilor.
Pe cea de-a doua linie se va afla numărul total m al cărărilor care unesc sate ale elfilor. Fiecare dintre următoarele m linii conține câte trei numere întregi, separate prin câte un spațiu. Primele două reprezintă numerele de ordine a două sate care sunt legate printr-o cărare. Cel de-al treilea număr reprezintă lungimea cărării care unește cele două sate.
Fișierul de ieșire OUTPUT.TXT trebuie
să conțină n - 1 linii.
Pe fiecare dintre acestea se va afla un număr care va reprezenta distanța minimă dintre satul natal al elfului și unul dintre celelalte sate. Ordinea liniilor este dată de numerele de identificare ale satelor corespunzătoare (prima conține distanța minimă până la satul identificat prin 2, cea de-a doua conține distanța minimă până la satul identificat prin 3 și așa mai departe).
INPUT.TXT
4 5 1 2 4 1 3 2 2 3 1 2 4 2 3 4 6 OUTPUT.TXT 3 2 5
|