== include(page="template/taskheader" task_id="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 oraşe 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.

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

5343