U jednom selu ima \(n\) kuća. Želimo da izgradimo vodovod tako da do svake kuće dolazi voda: to postižemo time što gradimo bunare i povezujemo kuće cevima. Za svaku kuću \(i\) možemo ili da izgradimo bunar ili da je cevima povežemo sa nekim susednim kućama. Kroz svaku cev voda može da ide u proizvoljnom smeru. Ako su poznate cene izgradnje bunara u svakoj kući i cene povezivanja kuća cevima, napiši program koji izračunava najmanju cenu potrebnu da svaka kuća dobije vodu.
Sa standardnog ulaza se učitava broj kuća \(n\) (\(1 \leq n \leq 5\cdot 10^4\)), zatim \(n\) brojeva koji predstavljaju cene izgradnje bunara za svaku kuću, a zatim do kraja ulaza cene izgradnji cevi (po tri cela broja u redu, gde prva dva broja predstavljaju različite kuće, a treći cenu izgradnje cevi između tih kuća, pri čemu ukupan broj cevi ne prelazi \(10^6\)). Brojevi kuća su od 1 do \(n\).
Na standardni izlaz ispisati najmanju cenu izgradnje vodovoda.
3 1 2 2 1 2 1 2 3 1
3
Najbolje je napraviti bunar u kući 1 i povezati druge dve kuće cevima sa njom.
4 2 2 2 2 1 2 5 1 3 5 1 4 5 2 3 5 2 4 5 3 4 5
8
Najbolje je da svaka kuća dobije svoj bunar.