Un tânăr elf dorește să viziteze toate satele locuite de elfi. El dorește să pornească din satul său, să viziteze fiecare sat o singură dată și să se întoarcă în satul său.
     Elful trebuie să își aleagă traseul astfel încât distanța totală a drumului său să fie minimă.
     El are la dispoziție o hartă pe care sunt specificate distanțele dintre oricare două sate, urmând cărările obișnuite.
     Elful nu se va abate de la aceste cărări din motive de siguranță.
     Cele n sate ale elfilor sunt identificate prin numere cuprinse între 1 și n, iar satul natal al elfului care va pleca în această călătorie este cel identificat prin 1.

Fișierul de intrare INPUT.TXT conține pe prima linie numărul n al satelor elfilor.
     Fiecare dintre următoarele n linii va conține câte n numere. Aceste numere reprezintă distanțele dintre sate.

Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie lungimea totală a traseului elfului.
     Fiecare dintre următoarele n + 1 linii va conține numărul de ordine al unui sat.
     Ordinea liniilor va indica ordinea în care sunt parcurse satele de către elf.
     Evident, pe prima și pe ultima dintre aceste linii se va afla numărul 1.

  • există cel mult 20 de sate ale elfilor.
  • între oricare două sate există exact un drum.
  • este obligatoriu ca elful să viziteze toate satele.
  • dacă există mai multe trasee de lungime minimă, poate fi ales oricare dintre acestea.
  • elful va pleca întotdeauna din satul identificat prin 1 și va ajunge în același sat.
  • grupurile pot fi descrise în orice ordine.


  • INPUT.TXT
    5
    0 1 5 1 2
    1 0 3 7 2
    5 3 0 4 4
    1 7 4 0 2
    2 2 4 2 0

    OUTPUT.TXT
    11
    1
    4
    5
    3
    2
    1