lazy

Lazy

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

Poveste şi cerinţă...

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!

h2. Date de intrare

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

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~}$.

h2. Date de ieşire

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

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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N,M ≤ 200.000$
* $1 ≤ a{~i~}, b{~i~} ≤ N$
* $1 ≤ C1{~i~} < 10^17^$
* $-10^17^ < C2{~i~} < 10^17^$
* dacă există mai multe soluţii se acceptă oricare dintre ele

h2. Exemplu
table(example). |_. lazy.in |_. lazy.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3
1 2 1 7
2 3 3 2
1 3 2 3
| 1
3

|

h3. Explicaţie
 
...
 

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

5343