Într-un oras linistit din America, municipalitatea a promis alegatorilor sa construiasca linii de tramvai pe strazile orasului. Cetatenii care nu au autoturisme sunt interesati ca strada lor sa dispuna de tramvai si cer o despagubire din partea primariei în cazul în care pe strada lor nu se introduce o astfel de linie. Cetatenii care au masini personale sunt mai interesati de pastrarea linistii pe strada lor si cer o despagubire din partea primariei în cazul în care pe strada lor va trece tramvaiul. Din fondurile CIMAU (Comisia Internationala pentru Modernizarea Asezarilor Urbane, cu sediul in România), municipalitatea are posibilitatea sa construiasca (fara cheltuieli proprii) legaturi directe subterane între oricare doua puncte ale orasului cu conditia ca nici o linie de metrou construita sa nu coincida cu o strada.

Cerinta

Cunoscandu-se numarul de puncte (intersectii) si perechile de puncte între care exista strada, despagubirea ceruta de fiecare dintre cele doua categorii de cetateni pentru fiecare strada si stiind ca orice punct al orasului este capatul a cel putin o strada, sa se stabileasca strazile pe care municipalitatea trebuie sa construiasca linie de tramvai si punctele între care trebuie sa construiasca linie de metrou asfel încât din orice punct al orasului sa se poata ajunge (cu ajutorul mijloacelor de transport în comun) în orice alt punct al orasului si costul total (rezultat din plata despagubirilor) sa fie minim.

Date de intrare

Din fisierul tramvai1.in se citesc:
- de pe prima linie numarul n de intersectii si numarul s de strazi existente între aceste intersectii, cele doua valori fiind despartite printr-un spatiu.
- considerând intersectiile numerotate de la 1 la n, se citesc de pe urmatoarele s linii ale fisierului câte 4 numere reprezentând: cele doua numere ale intersectiilor din capete, suma ceruta de cetatenii care nu vor tramvai pe strada respectiva si despagubirea ceruta de cei care vor tramvai (numere naturale de cel mult 4 cifre fiecare).

Date de iesire

În fisierul tramvai1.out se va scrie numarul întreg reprezentând costul total al despagubirilor. Daca nu exista solutii, se va afisa în fisier mesajul NU.

Restrictii

• n <= 100
• s <= 5000

Exemple

Explicatie

Daca se construiesc 4 linii de tramvai (1-5, 2-3, 2-4 si 2-5 de exemplu) si o singura linie de metrou (3-5) se poate face legatura între orice doua puncte ale orasului si costul total al despagubirilor este 31.

prof. Rodica Pintea
Liceul de Informatica "Grigore Moisil" Bucuresti