Sweet Butter

Problem Background

Special for beginners, ^_^

Problem Description

Farmer John discovered the way to make the sweetest butter in all of Wisconsin: sugar. He puts sugar on a pasture, knowing that $N$ ($1 \le N \le 500$) cows will come to lick it, so he can make super-sweet butter that sells for a good price. Of course, he will pay an extra cost for the cows.

Farmer John is cunning. Like Pavlov before him, he knows he can train these cows to go to a particular 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 which pasture each cow likes (a pasture does not necessarily hold only one cow). Given the pastures where the cows are and the routes between pastures, find the pasture that minimizes the total distance all the cows have to travel (where he will put the sugar).

Input Format

The first line contains three numbers: the number of cows $N$, the number of pastures $P$ ($2 \le P \le 800$), and the number of roads between pastures $C$ ($1 \le C \le 1450$).

Lines $2$ to $N+1$: the pasture number where cow $1$ to cow $N$ currently is.

Lines $N+2$ to $N+C+1$: each line contains three numbers: the connected pastures $A, B$, and the distance between them ($1 \le D \le 255$). The connection is bidirectional.

Output Format

Output on one line the minimum total distance the cows must walk.

Sample Input

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

Sample Output

8

Hint

Placing the sugar at pasture $4$ is optimal.

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.