Naši nepriatelia majú graf. Graf má \(n\) vrcholov a \(m\) hrán. Hrany sú neorientované. V grafe môžu existovať slučky1 aj násobné hrany2.
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.
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.