Táto úloha nadväzuje na úlohu Elektrárne, odporúčame vám preto najprv prečítať zadanie tej úlohy.
Predchádzajúca úloha bola iba zjednodušením skutočnej úlohy. Jedným zo zanedbaných faktorov je to, že každá elektráreň produkuje iba určité množstvo elektriny. Neprodukuje jej teda neobmedzene veľa. Podobne každá domácnosť spotrebuje iba určité množstvo elektriny. Nakoniec, každý uzol má obmedzenie na množstvo elektriny, ktoré ním môže prechádzať.
Tieto obmedzenia nazývame jednotne limitom vrcholu, a je určené celým číslom $c$. Do žiadneho vrcholu $v$ nesmie vchádzať ani z neho vychádzať viac ako $c_v$ jednotiek elektriny.
Pýtame sa rovnakú otázku: koľko najviac elektriny vieme v súčte sprostredkovať domácnostiam, a ako?
Na prvom riadku vstupu sú dve celé čísla oddelené medzerou: počet vrcholov $n$ a počet hrán $m$. Platí $2 \leq n \leq 1\,000$. ($m$ je zhora obmedzené podmienkami, ktoré uvedieme neskôr.)
Nasleduje $n$ riadkov, $i$-ty z nich popisuje vrchol $i$ a obsahuje dve medzerou oddelené celé čísla $t, l$: typ vrcholu a jeho limit. $t$ je $0$ pre elektráreň, $1$ pre uzol a $2$ pre domácnosť. Platí $1 \leq l \leq 10^9$.
Posledných $m$ riadkov popisuje hrany grafu. Každý riadok pozostáva z troch medzerou oddelených čísel: odkiaľ hrana vychádza $a$, kam hrana vchádza $b$ a kapacita hrany $c$. Platí $0 \leq a, b < n$, $a \neq b$, $1 \leq c \leq 10^5$. Môžete predpokladať, že $a$ nie je domácnosť a $b$ nie je elektráreň. Pre každé $a, b$ je na vstupe najviac jedna hrana z $a$ do $b$.
Môžete predpokladať $m^2 \cdot C < 2 \cdot 10^9$, kde $C$ je najväčšia kapacita hrany.
Výstup má mať rovnaký formát ako v predchádzajúcej úlohe.
Na prvý riadok vypíšte $k$: počet hrán, po ktorých chcete poslať nejaké (nezáporné) množstvo elektriny.
Následne vypíšte $k$ riadkov, každý nech obsahuje tri čísla $a, b, f$ oddelené medzerou. V tomto poradí sú to: z ktorého vrcholu hrana vychádza, do ktorého vchádza, a množstvo elektriny posielanej po tejto hrane.
Množstvo prenášanej elektriny nemusí byť celočíselné. Kvôli nepresnostiam pri výpočtoch s desatinnými číslami vám ale odporúčame, aby ste našli riešenie, ktoré má tieto hodnoty celočíselné. Je zaručené, že existuje také riešenie.
5 7
1 8
2 4
2 16
1 4
0 10
4 3 6
4 1 2
0 3 5
0 2 3
0 1 7
3 1 7
3 2 4
4
3 1 3
3 2 1
4 3 4
4 1 2