D — Vízelvezető árkok

Minden alkalommal, amikor esik az eső John farmer földjén, egy kisebb tó keletkezik Bessie kedvenc lóheremezőjén. Ilyenkor a lóherét egy darabig elönti a víz, és jó sokáig tart, mire újra kihajt. John farmer ezért kiépített egy vízelvezető árkokból álló rendszert, amely egy közeli patakba vezeti el a vizet, hogy ne árassza el többé Bessie lóheremezőjét. Mivel John farmer kiváló mérnök, szabályozókat is felszerelt az árkok elejére, amelyekkel vezérelni tudja az egyes árkokba folyó víz sebességét.

John farmer nemcsak azt tudja, hogy az egyes árkok percenként hány liter vizet képesek átereszteni, de az árkok pontos elhelyezkedését is ismeri. Az árkok a tavacskából indulnak, egymásba torkollnak, végül a patakban végződnek egy potenciálisan összetett hálózatot alkotva.

Mindezen információk birtokában határozd meg, hogy maximálisan mekkora sebességgel lehet eljuttatni a vizet a tavacskából a patakba! A víz minden árokban csak egy irányba folyik, az azonban előfordulhat, hogy több árkon keresztül körbefolyik.

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset első sorában két, szóközzel elválasztott egész szám szerepel: N és M (0 ≤ N ≤ 200, 2 ≤ M ≤ 200). N a John farmer által kiásott árkok számát, M pedig az árkok metszéspontjainak a számát adja meg. Az 1-es számú metszéspont a tó, az M sorszámú metszéspont pedig a patak. A következő N sor mindegyikében három egész szám szerepel: S_i, E_i és C_i. S_i és E_i jelölik azokat a metszéspontokat, amelyek között az i-edik árok húzódik (1 ≤ S_i, E_i ≤ M). A víz ebben az árokban S_i-től E_i felé folyik. C_i (0 ≤ C_i ≤ 10 000 000) az a legnagyobb sebesség, amellyel a víz át tud folyni ezen az árkon.

A kimenet specifikációja

Minden tesztesetre egyetlen egész számot kell a kimenetre írni: azt a maximális sebességet, amellyel eltüntethető a víz a tavacskából.

Példa bemenet

5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

50