1. Takto sa obsadzuje graf

Naši nepriatelia majú graf. Graf má \(n\) vrcholov a \(m\) hrán. Hrany sú neorientované. V grafe môžu existovať slučky¹ aj násobné hrany².

Na začiatku nám nepatrí žiadna časť grafu. Vrcholy aj hrany grafu vieme postupne obsadzovať. Našim cieľom je najlacnejším možným spôsobom obsadiť všetky vrcholy. Nezáleží nám na tom, či a ktoré hrany počas toho obsadíme.

Pri obsadzovaní grafu budeme používať figúrky. Obsadzovanie grafu prebieha v kolách. V každom kole môžeme vykonať jednu z nasledujúcich akcií:

• Ukážeme prstom na vrchol \(v\), v ktorom je momentálne aspoň \(a_v\) figúrok. Tento vrchol sme tým obsadili a odteraz už navždy patrí nám.

• Zaplatíme \(b_v\) peňazí a pridáme do vrcholu \(v\) jednu novú figúrku. Toto môžeme spraviť pre ľubovoľný vrchol, bez ohľadu na to, či je už obsadený.

• Ukážeme prstom na hranu \(e\), pre ktorú platí, že vo vrcholoch, ktoré spája, je dokopy aspoň \(c_e\) figúrok. Túto hranu sme tým obsadili a odteraz už navždy patrí nám.

• Zadarmo presunieme figúrku po hrane, ktorá nám už patrí. Toto môžeme spraviť bez ohľadu na to, či sú koncové vrcholy dotyčnej hrany už obsadené.

Úloha

Pre daný graf a dané parametre jeho obsadzovania vypočítajte, za akú najnižšiu cenu vieme obsadiť všetky jeho vrcholy.

Formát vstupu

V prvom riadku vstupu sú dve celé čísla: počet vrcholov \(n\) a počet hrán \(m\). Vrcholy sú očíslované od 1 po \(n\).

V \(i\)-tom z nasledujúcich \(n\) riadkov sú dve celé čísla: hodnoty \(a_i\) a \(b_i\).

Posledných \(m\) riadkov popisuje hrany. Popis každej hrany tvoria tri celé čísla: čísla vrcholov, ktoré spája, a hodnota \(c_i\).

Obmedzenia

• \(1\leq n,m\leq 300\,000\)
• \(0\leq a_i,b_i,c_i\leq 1\,000\,000\)
• je päť testovacích sád, líšia sa veľkosťou parametrov \(n\) a \(m\).

Formát výstupu

Vypíšte jeden riadok a v ňom jedno celé číslo: najlacnejšiu celkovú cenu obsadenia všetkých vrcholov.

Príklady

Input:

3 2
10 5
20 10
10 3
1 2 22
2 3 200

Output:

140

Dáme \(10\) figúrok do vrcholu \(1\) (cena \(50\)) a obsadíme ho. Pridáme ďalších \(12\) figúrok do vrcholu \(1\)$ (cena \(60\)) a obsadíme hranu \(1 - 2\). Presunieme \(20\) figúrok z vrcholu \(1\) do vrcholu \(2\) a obsadíme aj ten (cena \(0\)). Pridáme tri figúrky do vrcholu \(3\) (cena \(30\)) a obsadíme ho, čím sme vyhrali.

Input:

5 4
5 1
5 1
5 100
5 100
10 100
1 3 5
2 4 5
3 4 10
4 5 10

Output:

10

Celý graf vieme obsadiť za celkovú cenu \(10\), ak to spravíme šikovne.