== include(page="template/taskheader" task_id="arb4") ==

Poveste şi cerinţă...

Se da un graf cu $N$ noduri si $M$ muchii. Primele $N - 1$ muchii formeaza un arbore partial de cost minim. Pentru fiecare muchie $i$ din arbore trebuie sa se spuna in cazul in care muchia $i$ este stearsa, cu ce muchie trebuie inlocuita astfel incat costul arborelui partial sa fie minim.

h2. Date de intrare

Fişierul de intrare $arb4.in$ ...

Fişierul de intrare $arb4.in$ va contine pe prima linie $2$ numere naturale $N$ si $M$. Pe urmatoarele $M$ linii se vor afla $3$ numere naturale $a b c$ reprezentand ca avem o muchie de la $a$ la $b$ de cost $c$. Primele $N - 1$ muchii din cele $M$ formeaza arborele initial.

h2. Date de ieşire

În fişierul de ieşire $arb4.out$ ...

Fişierul de ieşire $arb4.out$ va contine $N - 1$ linii. Pe linia $i$ se va afla indicele muchiei care ar fi folosita daca am elimina muchia $i$ din arbore. Daca muchia $i$ nu poate sa fie inlocuita afisati $-1$.

h2. Restricţii

* $1 ≤ V ≤ 100.000$
* $1 ≤ E ≤ 250.000$
* toate muchiile au costuri distincte
* primele $V - 1$ muchii formeaza un arbore partial de cost minim in graful dat

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 250.000$
* muchiile au costuri distincte doua cate doua din intervalul $[1,1.000.000.000]$
* primele $N - 1$ muchii formeaza un arbore partial de cost minim in graful dat
* nodurile si muchiile sunt numerotate de la $0$
* intre oricare doua noduri exista cel mult o muchie si nu exista muchie de la un nod la el insusi

h2. Exemplu

5
|

h3. Explicaţie
 
...

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