The Sweetest Butter Problem

Farmer John discovered a method to produce the sweetest butter in Wisconsin using sugar. He places sugar on a pasture and knows that his N cows will be attracted to it. Each cow is initially at her favorite pasture (a pasture may have multiple cows). Farmer John can signal the cows by ringing a bell, and they will travel to the pasture with the sugar.

Given the initial locations of the cows and a network of bidirectional routes between pastures, determine the pasture where placing the sugar minimizes the total distance that all cows must travel. In other words, if d(i, j) denotes the shortest distance between pasture i and pasture j, and the cows are initially located at pastures p₁, p₂, \dots, p_N, find the pasture x such that the value

is minimized. Output this minimum total distance.

inputFormat

The first line contains three space-separated integers: N (the number of cows), P (the number of pastures), and C (the number of routes).

The second line contains N space-separated integers representing the pasture numbers where each cow is initially located.

Each of the next C lines contains three space-separated integers: a, b, and d, where a and b are pasture numbers (1-indexed) and d is the distance between them. The routes are bidirectional.

outputFormat

Output a single integer: the minimum total distance all cows must travel to reach the pasture where the sugar is placed.

sample

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

2