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).
     Evident, pe prima dintre aceste linii se va afla numărul 1, iar pe ultima dintre ele se va afla numărul n.

  • există cel mult 2000 de sate ale elfilor.
  • între satele elfilor se află cel mult 5000 de cărări.
  • între oricare două sate există cel mult o cărare directă.
  • pe oricare cărare se poate circula în ambele sensuri.
  • lungimile cărărilor sunt cuprinse între 1 și 1000.
  • va exista întotdeauna cel puțin o posibilitate de a ajunge din satul natal al elfului în oricare dintre celelalte sate.


  • INPUT.TXT
    4
    5
    1 2 4
    1 3 2
    2 3 1
    2 4 2
    3 4 6

    OUTPUT.TXT
    3
    2
    5