Bitoniczny komiwojażer

To zadanie pochodzi z Kółka Informatycznego w Staszicu.

Limit pamięci: 64MB

W Bajtocji jest n miast, ponumerowanych od 1 do n, przy czym niektóre pary miast są połączone dwukierunkowymi drogami o rozmaitych długościach. Komiwojażer Bajtazar chciałby objechać wszystkie miasta Bajtocji, wstępując do każdego dokładnie raz, po czym wrócić do początkowego miasta trasy.

Bajtazar ma jednak jeszcze jedno, dodatkowe wymaganie: chciałby, aby kolejne miasta na trasie tworzyły ciąg bitoniczny, tj. ciąg m_1, m_2, ..., m_n spełniający warunek

m_1 < m_2 < ... < m_i > m_{i+1} > ... > m_n

W tym zapisie parametr i może być dowolny, w szczególności może być równy n (i wtedy mamy ciąg rosnący) lub 1 (ciąg malejący).

Pomóż Bajtazarowi odnaleźć najtańszą trasę tej postaci, lub stwierdzić, że żadna taka trasa w Bajtocji nie istnieje.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite n oraz m (2 <= n <= 200,000, 1 <= m <= 500,000).
Kolejne m wierszy zawiera opisy bajtockich dróg, z których każdy składa się z trzech liczb całkowitych dodatnich a_i,b_i,w_i (a_i <= b_i <= n, a_i != b_i, w_i <= 10^9), oznaczających miasta połączone drogą i długość drogi. Każda para miast jest połączona co najwyżej jedną dwukierunkową drogą.

Wyjście

W jedynym wierszu wyjścia należy wypisać albo jedno słowo NIE, jeżeli nie istnieje trasa poszukiwana przez Bajtazara, lub jedną liczbę całkowitą oznaczającą długość najkrótszej takiej trasy.

Przykład

Dla danych:
4 5
1 2 2
1 3 3
2 3 3
3 4 4
1 4 1

Poprawnym wyjściem jest:
10


A dla danych:
4 4
1 3 1
1 4 1
2 3 1
2 4 1

Poprawnym wyjściem jest:
NIE