Farmer John está tão preguiçoso que não quer manter os caminhos para seus $N$ pastos ($5\le N\le10{,}000$), numerados $1\ldots N$. Cada um tem uma vaca. Quer remover o máximo dos $P$ caminhos ($N-1\le P\le100{,}000$) mantendo conexão. Determine os $N-1$ a manter.

Caminho bidirecional $j$ conecta $S_j,E_j$ ($1\le S_j\le N;1\le E_j\le N;S_j\ne E_j$), leva tempo $L_j$ ($0\le L_j\le1{,}000$). Há no máximo um direto por par.

As vacas estão tristes pela redução do transporte. Visite cada uma ao menos uma vez ao dia. Cada visita a $i$, mesmo passando, exige falar por $C_i$ ($1\le C_i\le1{,}000$).

Durma toda noite no mesmo pasto escolhido até se recuperarem. Falará com sua vaca ao menos ao acordar e à noite ao voltar para dormir.

Se FJ mantém seus caminhos e você escolhe o pasto ótimo para dormir, ache o mínimo tempo diário para visitar cada vaca ao menos uma vez.

Nas primeiras $10$ submissões receberá resultados em parte dos testes reais.

Entrada

• Linha $1$: inteiros $N,P$ separados por um espaço.

• Linhas $2\ldots N+1$: linha $i+1$, inteiro $C_i$.

• Linhas $N+2\ldots N+P+1$: linha $N+j+1$, inteiros $S_j,E_j,L_j$ separados por espaços.

Saída

• Linha $1$: inteiro, tempo total incluindo duas visitas à vaca do pasto onde dorme.

Exemplos

Entrada 1

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6
4 5 12

Saída 1

176

Explicação

              +-(15)-+
             /        \
            /          \
     1-(5)-2-(5)-3-(6)--5
            \   /(17)  /
         (12)\ /      /(12)
              4------+

Mantenha estes caminhos:

     1-(5)-2-(5)-3      5
            \          /
         (12)\        /(12)
             *4------+

Acorde em $4$, visite $4,5,4,2,3,2,1,2,4$ e leve $176$ antes de dormir.

Subtarefas

Pontos: $300$

Autores do problema: David Benjamin e Jacob Steinhardt, 2008