На училишниот натпревар, како што знаете, нема ранг листа, а секој ученик е заинтересиран да си го спореди својот резултат со резултатот на останатите.

Контактот меѓу двајца ученици може да е директен или индиректен. Контактот е директен ако двајца ученици може директно да комуницираат меѓусебно, а ако ученик X има контакт со Y, а Y со Z, тогаш сметаме дека X има индиректен контакт со Z, преку „мрежа“ од контакти.

Директните контакти знаат да бидат „зафркнати“, затоа што кога некои ученици комуницираат со други ученици не се трудат доволно да ги пренесат информациите најпрецизно што може. Некогаш дури и намерно се кажуваат грешни информации, во одредени комуникации.

Затоа, за сите постојни директни комуникации, воведена е бројна оценка за квалитетот на пренос на информациите, наречена Индекс на точност (ИТ) - која може да е каков било цел број (негативен број би означувал многу лош квалитет на пренос на информациите).

Во натпреварите учествуваат вкупно N ученици, означени со броевите од 1 до N. Вкупно има воспоставено M директни контакти, и секој од нив се опишува со вредностите A_i, B_i и C_i, со значење дека учениците A_i и B_i можат директно да комуницираат со Индекс на точност C_i.

Учениците сакаат за следната година да изберат само дел од директните контакти, за да направат мрежа во која секој ќе може да има контакт со секого. Притоа, сакаат таа мрежа да е што посигурна, односно сакаат да ја најдат таа мрежа која ќе има најголем можен вкупен ИТ (збир од секој ИТ, на секој директен контакт кој учествува во мрежата).

Ваша задача е да направите програма што го пресметува вкупниот ИТ на најсигурната мрежа што може да биде формирана. Ако не е можно да се направи мрежа во која секој ќе има контакт со секого (директно или индиректно), треба да се отпечати "N".

Влез

Првиот ред од влезот содржи два цели броја: N (2 ≤ N ≤ 100 000) и M (0 ≤ M ≤ 200 000), бројот на ученици, и бројот на контакти, соодветно.

Следните M редови содржат по три цели броја: A_i, B_i и C_i (1 ≤ A_i, B_i ≤ N, A_i ≠ B_i, −10⁶ ≤ C_i ≤ 10⁶), што означуваат дека учениците A_i и B_i имаат директен контакт со Индекс на точност C_i. Еден директен контакт ќе биде опишан точно со една тројка (на пример, не може да се појават истовремено тројки од типот (1, 2, 10), (1, 2, 5) или (2, 1, 7)).

Забелешка.
Во тест примери кои носат 15 поени важи: N ≤ 10, M ≤ 10, а C_i < 0
Во следни тест примери кои носат 15 поени важи: N ≤ 1 000, M ≤ 2 000, а C_i < 0
Во следни тест примери кои носат 30 поени важи: N ≤ 1 000, M ≤ 2 000.

Излез

Отпечатете еден цел број – максималниот можен вкупен ИТ на најсигурната можна мрежа што може да биде формирана, или "N" - кога воопшто не е можно да се направи мрежа.

Ограничувања

Временско ограничување: 400 milliseconds
Мемориско ограничување: 64 megabytes

Примери

влез
4 5
1 2 -1 
2 3 -5 
3 4 -3 
4 1 -2 
4 2 -3

излез
-6

влез
5 4
1 2 5 
2 3 2 
3 1 -1 
4 5 0

излез
N

Објаснување за првиот пример.
Во првиот пример, можно е да се воспостави најсигурна мрежа со избирање на врските меѓу: (1, 2) со ИТ -1, (3, 4) со ИТ -3, и (4, 1) со ИТ -2, што дава вкупен ИТ од (-1) + (-3) + (-2) = -6.

Објаснување за вториот пример.
Во вториот пример, не постои начин учениците 1, 2, 3 да комуницираат со учениците 4 и 5, што значи дека не може да се изгради целосна мрежа. Затоа, одговорот е „N“.