P2935 [USACO09JAN] Best Spot S

John owns $P(1 \leq P \leq 500)$ pastures. Bessie especially likes $F(1\leq F \leq P)$ of them. All pastures are connected by $C(1 < C \leq 8000)$ bidirectional roads. The $i$-th road connects pastures $a_i$,$b_i$ $(1 \leq a_i \leq P,1 \leq b_i \leq P)$ and takes $T_i(1 \leq T_i < 892)$ units of time to traverse. As a cow who always wants to improve her lifestyle, Bessie hopes that one day she will wake up at a pasture where the average time to reach all $F$ pastures she likes is minimized. At which pasture should she sleep the day before? Please help Bessie find this best pasture. For example, consider the pasture layout shown below, where starred pastures are the most favored ones, and the numbers in brackets are the traversal times of the cow paths. ```cpp 1*--[4]--2--[2]--3 | | [3] [4] | | 4--[3]--5--[1]---6---[6]---7--[7]--8* | | | | [3] [2] [1] [3] | | | | 13* 9--[3]--10*--[1]--11*--[3]--12* ``` 下表显示了牧场 $4,5,6,7,9,10,11$ 和 $12$ 与贝茜最喜欢的牧场的各个距离、平均距离和最终求出的最佳牧场： ```cpp * * * * * * 最喜欢的牧场 * * * * * * 可能的 牧场 牧场 牧场 牧场 牧场 牧场 平均 最佳牧场 1 8 10 11 12 13 距离 ------------ -- -- -- -- -- -- ----------- 4 7 16 5 6 9 3 46/6 = 7.67 5 10 13 2 3 6 6 40/6 = 6.67 6 11 12 1 2 5 7 38/6 = 6.33 7 16 7 4 3 6 12 48/6 = 8.00 9 12 14 3 4 7 8 48/6 = 8.00 10 12 11 0 1 4 8 36/6 = 6.00 ** 最佳的 11 13 10 1 0 3 9 36/6 = 6.00 12 16 13 4 3 0 12 48/6 = 8.00 ``` From the table, in the sample setting, pasture $10$ has the smallest average distance to all pastures Bessie likes, making it the best pasture.

The first line contains three integers $P$,$F$,$C$. The next $F$ lines each contain a single integer, the index of a pasture that Bessie likes. The next $C$ lines each contain three integers $a_i$,$b_i$,$T_i$, indicating there is a bidirectional path between $a_i$ and $b_i$ with traversal time $T_i$.

Output a single integer, the index of the best pasture. If there are multiple best pastures, output the smallest index.

Translated by AASDFGHJKL (1035916). Translated by ChatGPT 5