În momentul în care orcii au început atacurile împotriva elfilor, transportul diferitelor bunuri între sate a devenit o problemă importantă.
    Consiliul Lunii a decis protejarea unora dintre cărările dintre sate cu ziduri magice care să nu permită accesul orcilor.
    Din păcate, resursele magice sunt limitate, motiv pentru care Consiliul Lunii a cerut un plan de amplasare a zidurilor pentru ca să se poată ajunge din fiecare sat în oricare altul (direct sau indirect) și energia totală necesară menținerii tuturor zidurilor să fie minimă.
    De asemenea, Consiliul Lunii a cerut un plan de rezervă. Pentru acest plan, energia totală necesară trebuie să fie cât mai apropiată de cea necesară pentru planul principal (eventual, există posibilitatea ca energia necesară să fie egală cu cea din planul principal, dar nu trebuie alese exact aceleași cărări).

Prima linie a fișierului de intrare INPUT.TXT conține numărul n al satelor elfilor.
    Cea de-a doua linie a fișierului conține numărul total m al cărărilor care leagă satele elfilor.
    Fiecare dintre următoarele m linii conține câte trei numere întregi, separate prin câte un spațiu. Primele două indică două sate care sunt legate printr-o cărare, iar al treilea indică energia necesară construirii zidurilor magice pe cărarea respectivă.

Prima linie a fișierului de ieșire OUTPUT.TXT trebuie să conțină numărul p al cărărilor pe care se vor construi ziduri magice potrivit planului principal.
    Fiecare dintre următoarele p linii va conține câte două numere întregi, separate printr-un spațiu, care vor identifica două sate între care există o cărare pe care ar trebui construite ziduri magice potrivit planului principal.
    Următoarea linie a fișierului va conține numărul q al cărărilor pe care se vor construi ziduri magice potrivit planului de rezervă.
    Fiecare dintre următoarele q linii va conține câte două numere întregi, separate printr-un spațiu, care vor identifica două sate între care există o cărare pe care ar trebui construite ziduri magice potrivit planului de rezervă.

  • numărul satelor elfilor este cuprins între 3 și 100;
  • numărul cărărilor dintre satele elfilor este cuprins între 2 și 1000;
  • energia necesară construirii zidurilor magice pe o cărare este un număr întreg cuprins între 1 și 10000;
  • cele n sate ale elfilor sunt identificate prin numere cuprinse între 1 și n;
  • va exista întotdeauna cel puțin o soluție;
  • pe cărările dintre sate se poate circula în ambele sensuri;
  • configurația cărărilor corespunzătoare planului principal trebuie să difere de configurația cărărilor corespunzătoare planului de rezervă;
  • dacă există două sau mai multe planuri de rezervă, atunci poate fi ales oricare dintre ele;
  • dacă există două sau mai multe planuri pentru care energia totală este minimă, atunci oricare dintre acestea poate fi plan principal și oricare dintre acestea poate fi plan de rezervă.


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

    OUTPUT.TXT
    3
    1 2
    2 3
    2 4
    3
    1 3
    2 3
    2 4