Farmer John a découvert le secret du beurre le plus sucré du Wisconsin : le sucre. S’il met un morceau dans les pâturages, les $N$ vaches ($1\le N\le500$) le lèchent et produisent un beurre très sucré vendu plus cher. Il dépense bien sûr l’argent supplémentaire en luxes pour les vaches.

FJ est rusé. Comme Pavlov jadis, il sait entraîner les vaches à venir dans un pâturage au son d’une cloche. Il y mettra le sucre et sonnera en milieu d’après-midi pour un lait parfait à la traite du soir.

Chaque vache séjourne dans un pâturage donné, pas forcément seule. D’après leurs positions et les chemins, trouvez le pâturage pour le sucre minimisant la distance totale parcourue au son de la cloche. Les champs sont assez reliés pour qu’une solution existe toujours.

Entrée

• Ligne $1$ : entiers séparés par des espaces, nombre de vaches $N$, de pâturages $P$ ($2\le P\le800$), de chemins $C$ ($1\le C\le1{,}450$). Numéros uniques $1\ldots N$ pour les vaches, $1\ldots P$ pour les pâturages.

• Lignes $2\ldots N+1$ : un entier, le pâturage d’une vache ; celle $i$ est à la ligne $i+1$.

• Lignes $N+2\ldots N+C+1$ : trois entiers séparés par des espaces, deux pâturages et une longueur. Chemins bidirectionnels, au plus un direct par paire. Les deux premiers entiers dans $1\ldots P$, le troisième dans $1\ldots225$.

Sortie

• Ligne $1$ : entier, distance totale minimale des vaches vers le pâturage au sucre.

Exemples

Entrée 1

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

Sortie 1

8

Remarque

Le schéma montre géométriquement les liaisons :

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

En plaçant le sucre au pâturage $4$, la vache $1$ parcourt $3$ unités, la $2$ en parcourt $5$, la $3$ en parcourt $0$, total $8$.

Auteur du problème : Greg Galperin, 2001