Problem Description

Farmer John has discovered the method to make the sweetest butter in all of Wisconsin: sugar.

By placing the sugar in a pasture, he knows that N cows will come to lick it, allowing him to produce super-sweet butter that can be sold at a high price.

Of course, he will incur extra costs for the cows.

Farmer John is cunning. Like Pavlov of old, he knows he can train these cows to go to a specific pasture when they hear a bell.

He plans to place the sugar there and ring the bell in the afternoon so that he can milk the cows in the evening.

Farmer John knows which pasture each cow prefers (a pasture may not have only one cow).

Given the location of each cow and the routes between pastures, determine the pasture where the sum of the distances traveled by all cows to reach it is minimized (he will place the sugar there).

The data guarantees that at least one pasture is connected to all pastures where cows reside.

Input Format
Line 1: Three integers: the number of cows N, the number of pastures P, and the number of paths C.
Lines 2 to N+1: Line i+1 contains the pasture number where cow i is located.
Lines N+2 to N+C+1: Each line contains three integers: connected pastures A, B, and the distance D between them. The connection is bidirectional.

Output Format
A single line containing the minimum total distance the cows must travel.

Data Range
1 ≤ N ≤ 500
2 ≤ P ≤ 800
1 ≤ C ≤ 1450
1 ≤ D ≤ 255

Input Sample:

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

Output Sample:

8