În "centrul vechi al oraşului Copenhaga":http://www.denstoredanske.dk/@api/deki/files/27202/=48693232.jpg nu circulă maşini. De aceea, companiile de turism parchează autobuzele de hop-on hop-off în apropierea intersecţiilor de la margine. Oraşul este modelat astfel încât între oricare două intersecţii există un drum simplu unic. Intersecţiile de la extremitatea unei singure străzi sunt staţiile de autobuz, iar cele care leagă mai multe străzi - obiective turistice.
Fiecare stradă din Copenhaga are asociat un _avantaj_. De exemplu, pe străzile cu avantaj negativ sunt strategic poziţionaţi tinerii de la organizaţiile nonprofit în căutare de donaţii, iar pe străzile cu avantaj pozitiv - magazinele cu bere _aproape_ gratis. Suma avantajelor străzilor care formează un drum este avantajul acelui drum. Un drum simplu de avantaj $0$, cu staţii de autobuz în extremităţi distincte, se numeşte _ecotraseu_.
Fiecare stradă din Copenhaga are asociat un _avantaj_. De exemplu, pe străzile cu avantaj negativ sunt strategic poziţionaţi tinerii de la organizaţiile nonprofit în căutare de donaţii, iar pe străzile cu avantaj pozitiv - magazinele cu bere _aproape_ gratis. Suma avantajelor străzilor care formează un drum este avantajul acelui drum. Un drum simplu de avantaj $0$, cu staţii de autobuz distincte în extremităţi, se numeşte _ecotraseu_.
Companiile de turism ştiu că în oraş există un ecotraseu, dar ar vrea să gasească şi extremităţile unuia pentru a parca autobuzele în ele.
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$ $<=$ $x$, $y$ $<=$ $N$ $<=$ $100.000$
* $|a|$ $<=$ $10.000$
* $1$ $<=$ $x$, $y$ $<=$ $N$ $<=$ $10^5^$
* $|a|$ $<=$ $10^4^$
* $1$ $<=$ $T$ $<=$ $20$
* Cel mult $10$ teste au $1$ $<=$ $N$ $<=$ $10^4^$
* Cel mult $10$ teste au $10^4^$ $<=$ $N$ $<=$ $10^5^$
h2. Exemplu
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 test, drumul $2$ - $1$ - $3$ este un ecotraseu.
== include(page="template/taskfooter" task_id="ecotraseu") ==
