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 n miast ponumerowanych liczbami od 1 do n. Niektóre pary miast są połączone jednokierunkowymi drogami. Naczelny budowniczy Bajtocji wybrał m dróg, które jego zdaniem nadają się do odnowy. Dla każdej z tych dróg przewidział koszt jej naprawy.</p>

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.

입력 형식

W pierwszym wierszu wejścia podane są dwie liczby całkowite n i m (2 ≤ n ≤ 300, 1 ≤ m ≤ n²) określające liczbę miast w Bajtocji oraz liczbę jednokierunkowych dróg nadających się do renowacji. W kolejnych m wierszach wejścia znajdują się po trzy liczby całkowite x, y i k (1 ≤ x, y ≤ n, 0 ≤ k ≤ 10⁵) oznaczające, że odnowienie drogi prowadzącej z miasta x do miasta y kosztuje k bajtalarów. Każda uporządkowana para x, y 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.

출력 형식

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.

예제 입력 1

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

예제 출력 1

16

예제 입력 2

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

예제 출력 2

NIE