Farmer John ha scoperto il segreto del burro più dolce del Wisconsin: zucchero. Un cubetto nei pascoli viene leccato dalle $N$ mucche ($1\le N\le500$), producendo burro dolcissimo vendibile a prezzo migliore. Il denaro extra va ovviamente in lussi per loro.

FJ è astuto. Come Pavlov un tempo, sa addestrarle ad andare in un pascolo al suono di una campana. Metterà lì lo zucchero e suonerà a metà pomeriggio, per latte perfetto alla mungitura serale.

Ogni mucca sta in un pascolo dato, non necessariamente sola. Da posizioni e sentieri trova dove mettere lo zucchero per minimizzare la distanza totale al suono della campana. I campi sono abbastanza connessi da garantire sempre una soluzione.

Input

• Riga $1$: interi separati da spazi, mucche $N$, pascoli $P$ ($2\le P\le800$), sentieri $C$ ($1\le C\le1{,}450$). Numeri unici $1\ldots N$ per mucche e $1\ldots P$ per pascoli.

• Righe $2\ldots N+1$: intero, pascolo di una mucca; la $i$ è alla riga $i+1$.

• Righe $N+2\ldots N+C+1$: tre interi separati da spazi, due pascoli e lunghezza. Sentieri bidirezionali, al massimo uno diretto per coppia. Primi due in $1\ldots P$, terzo in $1\ldots225$.

Output

• Riga $1$: intero, distanza totale minima delle mucche al pascolo con zucchero.

Esempi

Input 1

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

Output 1

8

Spiegazione

Il diagramma mostra geometricamente i collegamenti:

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

Con zucchero in $4$, mucca $1$ percorre $3$ unità, la $2$ percorre $5$, la $3$ percorre $0$, totale $8$.

Autore del problema: Greg Galperin, 2001