Description

Farmer John has found a way to make the sweetest butter in all of Wisconsin: sugar.

If he puts sugar on a pasture, he knows $N$ cows will come and lick it, letting him make super-sweet butter that sells for a good price. Of course, the cows must walk to the sugar.

Farmer John is cunning. Like Pavlov, he knows he can train the cows to go to a specific pasture when they hear a bell. He plans to put the sugar there and ring the bell in the afternoon so that he can milk them in the evening.

Farmer John knows where each cow currently is (a pasture can have more than one cow). Given the current pasture of each cow and the roads between pastures, find the pasture that minimizes the sum of walking distances for all cows to reach it (he will place the sugar there).

Input Format

• The first line contains three integers $N, P, C$, the number of cows, the number of pastures, and the number of roads, respectively.
• Lines $2$ to $N+1$: each line contains one integer. Line $i$ gives the pasture index where cow $i$ is located.
• Lines $N+2$ to $N+C+1$: each line contains three integers $A, B, D$, meaning there is an undirected road of length $D$ between pastures $A$ and $B$.

Output Format

Output a single integer: the minimum possible sum of distances that all cows must walk.

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

8

Hint

Constraints

For all testdata, $1 \le N \le 500$, $2 \le P \le 800$, $1 \le A, B \le P$, $1 \le C \le 1450$, $1 \le D \le 255$.

Sample Explanation

Diagram:

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

Putting the sugar at pasture $4$ is optimal.

Translated by ChatGPT 5