Farmer John descobriu o segredo da manteiga mais doce de Wisconsin: açúcar. Pondo um cubo nos pastos, sabe que as $N$ vacas ($1\le N\le500$) o lamberão e produzirão manteiga muito doce que poderá vender mais cara. Claro, o dinheiro extra vai para luxos para elas.

FJ é astuto. Como Pavlov antigamente, sabe treiná-las para ir a certo pasto ao ouvir um sino. Põe o açúcar lá e toca no meio da tarde para obter leite perfeito na ordenha à noite.

Cada vaca fica num pasto dado, não necessariamente sozinha. Pelas posições e caminhos, encontre onde pôr o açúcar para minimizar a distância total ao toque do sino. Os campos são suficientemente conectados para sempre haver solução.

Entrada

• Linha $1$: inteiros separados por espaços, vacas $N$, pastos $P$ ($2\le P\le800$), caminhos $C$ ($1\le C\le1{,}450$). Números únicos $1\ldots N$ para vacas e $1\ldots P$ para pastos.

• Linhas $2\ldots N+1$: inteiro, pasto de uma vaca; a $i$ está na linha $i+1$.

• Linhas $N+2\ldots N+C+1$: três inteiros separados por espaços, dois pastos e comprimento. Caminhos bidirecionais, no máximo um direto por par. Primeiros dois em $1\ldots P$, terceiro em $1\ldots225$.

Saída

• Linha $1$: inteiro, distância total mínima das vacas até o pasto com açúcar.

Exemplos

Entrada 1

3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5

Saída 1

8

Explicação

O diagrama mostra geometricamente as conexões:

          P2  
 P1 @--1--@ C1
     \    |\
      \   | \
       5  7  3
        \ |   \
         \|    \ C3
       C2 @--5--@
          P3    P4

Pondo açúcar em $4$, a vaca $1$ anda $3$ unidades, a $2$ anda $5$, a $3$ anda $0$, total $8$.

Autor do problema: Greg Galperin, 2001