Renowacja dróg [A]

Limit pamięci: 128 MB

Większość dróg w Bajtocji znajduje się w opłakanym stanie. Król Bajtocji, przychylając się do licznych próśb swoich poddanych, postanowił przeprowadzić renowacje niektórych dróg. W Bajtocji jest miast ponumerowanych liczbami od do . Niektóre pary miast są połączone jednokierunkowymi drogami. Naczelny budowniczy Bajtocji wybrał dróg, które jego zdaniem nadają się do odnowy. Dla każdej z tych dróg przewidział koszt jej naprawy.

Król chce, aby każdy obywatel Bajtocji mógł osobiście odczuć poprawę jakości dróg. Założył, że mieszkańcy dowolnego miasta będą się czuć zadowoleni, jeśli będzie można wjechać do ich miasta oraz wyjechać z ich miasta co najmniej jedną odnowioną drogą. Naprawy należy zaplanować tak, by ich sumaryczny koszt był jak najmniejszy. Stworzenie planu renowacji dróg, który spełni wymagania króla, przypadło w udziale Tobie.

Wejście

W pierwszym wierszu wejścia podane są dwie liczby całkowite i (, ) określające liczbę miast w Bajtocji oraz liczbę jednokierunkowych dróg nadających się do renowacji. W kolejnych wierszach wejścia znajdują się po trzy liczby całkowite , i (, ) oznaczające, że odnowienie drogi prowadzącej z miasta do miasta kosztuje bajtalarów. Każda uporządkowana para wystąpi na wejściu co najwyżej raz. Zauważ, że może istnieć droga zaczynająca się i kończąca w tym samym mieście.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna liczba całkowita określająca najmniejszy możliwy koszt przeprowadzenia renowacji zgodnie z założeniami króla lub słowo NIE, jeśli nie jest możliwe przygotowanie planu, który spełnia wymagania króla.

Przykład

Dla danych wejściowych:

4 6
1 2 1
2 1 2
1 3 3
3 1 4
3 2 5
4 4 6

poprawną odpowiedzią jest:

16

natomiast dla danych wejściowych:

4 4
1 2 5
2 3 4
3 1 8
2 4 7

poprawną odpowiedzią jest:

NIE

Autor zadania: Robert Kozikowski.