Obwód elektryczny

Limit pamięci: 64 MB

Kapitan Bajtazar bada planetę Vicugna, która jest wysoce nietypowa pod każdym względem - obok wielu interesujących faktów (na przykład obecności gatunku różowych lam), planeta posiada zmienne pole magnetyczne. W celu zbadania zjawisk magnetycznych Bajtazar wybrał punktów węzłowych na planecie i połączył je między sobą przewodami elektrycznymi. W przewodach tych, na skutek działania pola magnetycznego, popłynął prąd o pewnym natężeniu, być może różnym dla różnych przewodów. Prąd płynie zgodnie z prawami fizyki - każdym przewodem tylko w jednym kierunku, a w każdym węźle suma natężeń prądów wpływających musi być równa sumie natężeń prądów wypływających.

Bajtazar chce teraz zainstalować na przewodach amperomierze, które wyznaczą natężenia prądów. Oczywiście mógłby zamontować taki amperomierz na każdym przewodzie, ale to operacja długa, męcząca i oczywiście bardzo droga. Bajtazar kombinuje zatem, jak zredukować koszty do minimum - wiadomo przecież, że da się wyznaczyć natężenia prądu w niektórych przewodach na podstawie pozostałych.

Każdy z przewodów ma swój koszt zainstalowania na nim miernika. Koszt ten może być dodatni (trzeba spalić cenne paliwo i poświęcić jeden amperomierz) lub ujemny (Bajtazar spodziewa się w niektórych miejscach znaleźć piękne Vicugnanki cenne minerały, co wynagrodzi mu straty). Znajdź taki sposób instalacji amperomierzy (czyli odpowiedni zbiór przewodów), który ma najmniejszy możliwy sumaryczny koszt, a pozwala na wyznaczenie natężeń we wszystkich przewodach.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite i (, ) oznaczające liczbę węzłów i liczbę przewodów. W kolejnych wierszach podane są opisy przewodów: -ty wiersz zawiera trzy liczby całkowite , , (, , ) oznaczające, że -ty przewód łączy węzły i , a koszt zamontowania na nim amperomierza to . Każda para węzłów jest połączona co najwyżej jednym przewodem.

Wyjście

W jedynym wierszu wyjścia wypisz jedną liczbę całkowitą - minimalny koszt odpowiedniego zbioru amperomierzy.

Przykład

Dla danych wejściowych:

4 6
1 2 -1
3 4 6
4 1 4
2 3 3
2 4 2
1 3 3

poprawną odpowiedzią jest:

4

Autor zadania: Lech Duraj.