Dupla de Postos
Uma região possui n vilarejos ligados por n-1 estradas bidirecionais, sem ciclos. Cada estrada tem um comprimento positivo, e o vilarejo v possui dv solicitações de atendimento.
A administração instalará exatamente dois postos, obrigatoriamente nas duas extremidades de uma mesma estrada. Cada solicitação será atendida pelo posto mais próximo, medindo a distância pelas estradas; o custo total é a soma, sobre os vilarejos, de dv vezes a distância até o posto escolhido. Determine o menor custo possível. Em caso de empate, escolha a estrada cujo par de extremidades ordenado (min(u,v), max(u,v)) é lexicograficamente menor.
Input
A primeira linha contém n. A segunda contém d1, ..., dn. Cada uma das próximas n-1 linhas contém u v w, descrevendo uma estrada de comprimento w.
Restrições:
2 ≤ n ≤ 200000; 0 ≤ dv ≤ 1000; 1 ≤ w ≤ 1000. As estradas formam uma árvore.
Output
Imprima três inteiros: o custo mínimo e os dois extremos da estrada escolhida, em ordem crescente.
Samples
Sample 1
Input
3 2 1 2 1 2 2 2 3 3
Output
4 2 3
Abrindo postos nos vilarejos 2 e 3, as duas solicitações do vilarejo 1 percorrem distância 2; o custo é 4.