h2. Date de intrare

Pe prima linie a fişierului de intrare $ecotraseu.in$ se găseşte numărul $N$ de intersecţii. Pe următoarele linii se găsesc triplete de numere separate prin spaţiu, unde fiecare triplet de forma $x$ $y$ $a$ reprezintă cele două intersecţii $x$ şi $y$, urmate de avantajul străzii $a$. Fişierul se termină cu caracterul sfârşit de linie.

Pe prima linie a fişierului de intrare $ecotraseu.in$ se găseşte numărul $T$ de teste. Fiecare test începe apoi pe linie nouă. Pe prima linie a unui test se găseşte numărul $N$ de intersecţii. Pe următoarele linii se găsesc triplete de numere separate prin spaţiu, unde fiecare triplet de forma $x$ $y$ $a$ reprezintă cele două intersecţii $x$ şi $y$, urmate de avantajul străzii $a$. Fişierul se termină cu caracterul sfârşit de linie.

h2. Date de ieşire

Fişierul de ieşire $ecotraseu.out$ conţine o singură linie cu două numere separate prin spaţiu, care indică extremităţile unui ecotraseu. Fişierul se termină cu caracterul sfârşit de linie.

Fişierul de ieşire $ecotraseu.out$ conţine $T$ linii cu câte două numere separate prin spaţiu, care indică extremităţile unui ecotraseu pentru un test dat. Fişierul se termină cu caracterul sfârşit de linie.

h2. Restricţii

* $1$ $<=$ $T$ $<=$ $20$

* $1$ $<=$ $x$, $y$ $<=$ $N$ $<=$ $100.000$
* $|a|$ $<=$ $10.000$

table(example). |_. ecotraseu.in |_. ecotraseu.out |
| 2

  2

  1 2 0

| 1 2
|
| 3

  3

  1 2 -1
  1 3 1

| 2 3

| 1 2
  2 3

|
h3. Explicaţie

În primul exemplu, drumul $1$ - $2$ este un ecotraseu. În al doilea exemplu, drumul $2$ - $1$ - $3$ este un ecotraseu.

Sunt două teste. În primul test, drumul $1$ - $2$ este un ecotraseu. În al doilea exemplu, drumul $2$ - $1$ - $3$ este un ecotraseu.

== include(page="template/taskfooter" task_id="ecotraseu") ==