Revista GInfo este tipătită în două tipografii și este distribuită în N orașe. În fiecare lună jumătate dintre orașele în care este difuzată GInfo primesc reviste de la una dintre tipografii, iar cealaltă jumătate de la cealaltă tipografie.
De la fiecare tipografie pornesc câte N / 2 camioane încărcate cu reviste. Fiecare dintre cele N camioane trebuie să ajungă la unul dintre cele N orașe. Departamentul de distribuție al GInfo dorește să determine care orașe vor fi deservite de prima tipografie și care de cea de-a doua, astfel încât distanța totală pe care o vor parcurge camioanele să fie minimă. Un camion va ajunge la orașul destinație pe cel mai scurt drum posibil. Între orașe se află un număr total de M străzi pe care se poate circula în ambele sensuri. Pentru fiecare stradă sunt cunoscute orașele pe care le unește, precum și lungimea străzii. Orașele sunt identificate prin numere cuprinse între 1 și N, iar tipografiile se află în orașele identificate prin 1 și 2. Evident, distanța dintre tipografia din orașul 1 și orașul 1 este 0, iar distanța dintre tipografia din orașul 2 și orașul 2 este tot 0.
Fișierul de intrare GINFO.IN conține pe prima linie numărul natural N,
reprezentând numărul orașelor, precum și numărul natural M,
reprezentând numărul străzilor. Cele două numere sunt separate printr-un spațiu. Fiecare dintre următoarele M, linii va conține câte trei numere naturale x, y și L, cu semnificația: există o stradă de lungime L între orașele x și y.
Fișierul de ieșire GINFO.OUT trebuie să conțină două linii, pe fiecare aflându-se câte N / 2 numere naturale, separate prin câte un spațiu. Numerele de pe prima linie reprezintă orașele deservite de prima tipografie, iar celel de pe a doua linie reprezintă orașele deservite de cea de-a doua tipografie.
GINFO.IN
6 8 1 2 5 1 4 8 1 6 7 2 3 6 3 4 5 3 6 2 4 5 3 5 6 2 GINFO.OUT 1 4 5 2 3 6
|