Fişierul intrare/ieşire:	lazy.in, lazy.out	Sursă	RMMS 2011 - Ziua 1
Autor	Andrei Parvu	Adăugată de	Andrei Parvu •andrei.12
Timp execuţie pe test	0.3 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Poti vedea testele pentru aceasta problema accesand atasamentele.

Vezi solutiile trimise | Statistici

Lazy

Toată lumea ştie că muncitorii din România sunt foarte leneşi. Unul dintre aceşti muncitori este Dorel, care lucrează pentru o companie care construieşte drumuri prin ţară. Ieri el a primit o nouă cerinţă: i s-au specificat N oraşe din România (numerotate de la 1 la N), M străzi bidirecţionale (numerotate de la 1 la M) care nu sunt încă construite, fiecare legând exact două oraşe; dintre aceste drumuri el trebuie să selecteze şi să construiască N-1 astfel încât toate oraşele să devină conectate. Din păcate aceasta problemă nu este foarte simplă pentru Dorel: fiecare drum i are asociat două costuri: C1_i – efortul care trebuie depus pentru a construi drumul si C2_i: C1_i * C2_i fiind profitul luat de pe urma construirii drumului. Bineînţeles Dorel vrea să muncească cât mai puţin posibil aşa că cel mai important lucru este ca suma costurilor drumurilor construite să fie minimă; dacă există mai multe moduri de a construi drumuri astfel încât costul total să fie minim, Dorel dorşte ca profitul total (suma profiturilor pentru fiecare drum) să fie maxim.
Voi trebuie să rezolvaţi problema lui Dorel!

Date de intrare

Pe prima linie a fişierului lazy.in se află două numere N şi M, numărul de oraşe, respectiv numărul de drumuri. Urmează M linii, a i-a din aceste linii are 4 numere naturale: a_i si b_i reprezentând oraşele pe care drumul i le leagă, C1_i şi C2_i.

Date de ieşire

Fişierul de ieşire lazy.out trebuie să conţină N-1 numere reprezentând indecşii (conform fişierului de intrare) drumurilor care trebuie alese de Dorel.

Restricţii

• 1 ≤ N,M ≤ 200.000
• 1 ≤ a_i, b_i ≤ N
• 1 ≤ C1_i < 10¹⁷
• -10¹⁷ < C2_i < 10¹⁷
• dacă există mai multe soluţii se acceptă oricare dintre ele

Exemplu

Cum se trimit solutii?