Sweet Butter

Farmer John has found the secret to making the sweetest butter in all of Wisconsin: sugar. He places a sugar cube out in the pastures. The $N$ cows ($1 \le N \le 500$) lick it and produce super-sweet butter, which sells for better prices. FJ spends the extra money on luxuries for the cows.

FJ is a sly farmer. Like Pavlov of old, he has trained the cows to go to a certain pasture when they hear a bell. He puts the sugar in that pasture, then rings the bell in the middle of the afternoon so that the evening's milking produces perfect milk.

FJ knows which pasture each cow spends her time in. More than one cow can be in the same pasture. You are given the pasture locations of the cows and a description of the paths that connect the pastures. Find the pasture to place the sugar cube so that the total distance the cows walk when FJ rings the bell is minimized. The fields are connected well enough that a solution always exists.

The first line contains three integers $N$, $P$ ($2 \le P \le 800$), and $C$ ($1 \le C \le 1450$), separated by spaces. $N$ is the number of cows, $P$ is the number of pastures, and $C$ is the number of paths. Cows are numbered 1 to $N$, and pastures are numbered 1 to $P$.

Each of the next $N$ lines contains one integer, the pasture where that cow is grazing. Cow $i$ is listed on line $i+1$.

Each of the next $C$ lines contains three integers: two pasture numbers and the length of the path between them. The length is between 1 and 225. Paths can be walked in either direction. No pair of pastures is connected by more than one path.

Print one integer: the minimum total distance the cows must walk to reach the pasture with the sugar cube.

The diagram below shows the connections geometrically.

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

If the cube is placed in pasture 4, cow 1 walks 3 units, cow 2 walks 5 units, and cow 3 walks 0 units. The total is 8.