5. Optimálna šifrovačka

Šifrovačky sú úžasné akcie. Bežne na šifrovačke dostanete nejakú zašifrovanú správu a keď ju vylúštite, dozviete sa, kde sa nachádza ďalšia šifra. Nasleduje presun terénom a ďalšie lúštenie. Je to skvelá možnosť, ako si precvičiť mozgové závity aj nohy.

Mnohí ľudia sa domnievajú, že poriadna šifrovačka nie je ani tak o šifrách, ako skôr o náročnosti trasy. O čo ťažšia je cesta a čím väčšia je šanca na prechladnutie, tým dlhšie sa budú účastníci chváliť svojou účasťou v nej. Ak k tomu pridáte výškové rozdiely, zlé počasie a možnosť zlomiť si pár končatín, dostanete nezabudnuteľnú hru.

Hlavný vedúci KSP sa rozhodol namiesto jesenného sústredenia spraviť najnezabudnuteľnejšiu šifrovačku všetkých čias. Sedemdňovú (a sedemnočnú) šifrovačku umiestnil do Vysokých Tatier. Na jeseň bude určite mokro a skalnaté tatranské končiare budú krásne šmykľavé.

Keď svoj úžasný plán prezradil ostatným vedúcim, nestretol sa s nadšením. Vedúci sa chytali za hlavy a snažili sa ho od toho odhovoriť. No márne. Kocky už boli hodené a jediné, čo ešte mohli spraviť, bolo upraviť cestu tak, aby deti nemuseli nikdy ísť do kopca. Hlavný vedúci si vyprosil aspoň to, aby vzniknutá trasa bola čo najdlhšia.

Úloha

Máte daný zoznam tatranských križovatiek a zoznam turistických chodníkov medzi nimi. Poznáte nadmorskú výšku každej križovatky a dĺžku každého chodníka. Zistite dĺžku najdlhšej klesajúcej (takej, ktorá neobsahuje stúpania ani roviny) trasy po týchto križovatkách.

Trasa môže začať a končiť na ľubovoľnej križovatke.

Formát vstupu

Prvý riadok obsahuje dve celé čísla \(n\) (\(1 \leq n \leq 100\,000\)) a \(m\) (\(0 \leq m \leq 1\,000\,000\)), ktoré udávajú počet križovatiek a počet chodníkov medzi nimi.

Ďalších \(n\) riadkov obsahuje jedno číslo \(v_i\) (\(1 \leq v_i \leq 1\,000\,000\,000\)), ktoré udáva nadmorskú výšku \(i\)-tej križovatky (križovatky sa číslujú od jednotky). Všetky nadmorské výšky sú navzájom rôzne.

Ďalších \(m\) riadkov obsahuje trojice čísel \(x_i\), \(y_i\), a \(c_i\) (\(1 \leq c_i \leq 1\,000\,000\,000\)), kde \(c_i\) je dĺžka chodníka medzi \(x_i\)-tou a \(y_i\)-tou križovatkou.

Vstupy v piatej sade sú pomerne veľké a očakávame, že pomalšie jazyky ako Python a Java nebudú stíhať. Ak používate tieto jazyky, zmierte sa s tým, že pravdepodobne dostanete len 4 body z 5 za program aj pri optimálnej časovej zložitosti. Ešte môžete skúsiť prepísať program do jazyka C++, ten je dosť rýchly.

Formát výstupu

Vypíšte jedno celé číslo – dĺžku najdlhšej klesajúcej trasy.

Príklad

Input:

6 6
100
50
300
47
20
15
1 3 10
3 2 40
2 1 50
4 2 70
5 3 60
5 6 30

Output:

130

Najdlhšia klesajúca cesta ide postupne po križovatkách 3 - 1 - 2 - 4.