5. Tarantulu za klobásu a tri dukáty

Veľký vezír Kárespes sedí na svojom zlatom tróne v trónnej saune vo svojom čiernom paláci. Para mu stúpa do hlavy a s ňou vysoké myšlienky o dokonalej ekonomike. Vezír Kárespes je totiž ekonomický mysliteľ a idealista.

Čo to už aj vymyslel. V jeho krajine žije kopa obchodníkov, priekupníkov, čarodejníc a čarodejníkov (aj čarodejníčat) a všetci potrebujú kupovať a predávať (aspoň to im vezír Kárespes natĺkol do hlavy). Samozrejme, keďže vezír je ekonomický idealista, nedovolí, aby sa v jeho krajine praktizoval voľný obchod, veď to by o chvíľu skrachovalo. Ekonomika musí byť vyvážená a dokonalá.

Hlavný princíp Kárespesovej ekonomiky je tzv. “zmeň a keš” (tak to nenazval vezír Kárespes, ale kto si má zapamätať ten latinský názov). Ten spočíva v tom, že dvaja ľudia si vymenia nejaký tovar (“zmeň”) a jeden za to druhému ešte aj niečo zaplatí (“keš”). Napríklad, Saxana dá Voldemortovi gumený nos, on jej dá elastické rukavice, a keďže gumený nos má väčšiu hodnotu, tak Voldemort ešte zaplatí Saxane zopár dukátov.

Samozrejme, nie je dovolené takýmto spôsobom obchodovať úplne ľubovoľne. Veľký vezír Kárespes každému poddanému vo svojej ríši nariadil, čo môže vymieňať za čo a koľko má pri tom platiť alebo dostať.

Navyše, aby v ríši nenastal chaos, zmätok, alebo krach, vezír zariadil, aby nebolo možné tento systém oblafnúť. Predstavte si, že by som si mohol u niekoho vymeniť žabu za mačku a u niekoho iného mačku za žabu a zarobiť na tom. Potom by som mohol chodiť od jedného k druhému, vymieňať a vymieňať a zarobiť neobmedzené množstvo peňazí. Vezír však na toto myslel a preto zariadil, aby žiadne takéto triky neboli možné.

Zatiaľ čo sa vezír Kárespes zvlhčuje v saune, rybár Asymptot ulovil zlatú rybku. A tá mu sľúbila, že mu dá úplne hocičo. Samozrejme iba jeden kus. A samozrejme, že nie úplne hocičo, ale nejaký tovar. A chudák rybár Asymptot rozmýšľa, čo si má vybrať. Pomôžete mu s tým?

Úloha

Dostanete počet predmetov a potom nariadenia, ako vezír Kárespes prikázal obchodovať s danými predmetmi. Každé nariadenie hovorí, ktorý predmet je možné vymeniť za ktorý a koľko za takúto výmenu dostanete peňazí. (Napríklad, ak čarodejnica z tmavého lesa dostala nariadenie, že má vymieňať mušie krídla za hadie chvosty a dať za to 5 dukátov, tak za ňou môže niekto prísť, dať jej mušie krídla, dostane hadie chvosty a ešte aj 5 dukátov. Nemôže však urobiť opačnú výmenu – dať hadie chvosty a dostať mušie krídla – pokiaľ čarodejnica nemá aj takéto nariadenie.)

Navyše platí, že ak sa z nejakého predmetu postupnými výmenami dostanete naspäť k tomu istému predmetu, nezarobíte na tom nič (ani neprerobíte).

Vašou úlohou je zistiť, koľko najviac peňazí môže rybár Asymptot zarobiť, ak si od zlatej rybky vypýta správny predmet.

Formát vstupu

Na prvom riadku su dve celé čísla \(n, m\) oddelené medzerou – počet predmetov a počet nariadení. Predmety si očíslujeme od \(0\) po \(n-1\).

Na ďalších \(m\) riadkoch sa nachádzajú popisy jednotlivých nariadení. Nariadenie je popísané na jednom riadku tromi celými číslami: \(a_i, b_i, c_i\). Číslo \(a_i\) určuje, ktorý tovar môže Asymptot dať, \(b_i\) určuje, ktorý dostane a \(c_i\) hovorí, koľko dukátov za takúto výmenu utŕži.

Platí \(1 \leq n, m \leq 10^6\), \(0 \leq a_i,b_i < n\) a \(|c_i| \leq 10^9\).

Formát výstupu

Na jediný riadkok vypíšte jedno celé číslo – najväčší počet dukátov, ktorý vie rybár Asymptot zarobiť, ak si od zlatej rybky vypýta správny predmet.

Príklady

Input:

4 3
0 1 -1
1 2 -1
2 3 -1

Output:

0

Neoplatí sa obchodovať.

Input:

4 5
0 1 1
1 2 -3
2 3 4
3 0 -2
2 0 2

Output:

4