生活を最適化したい Bessie は、Farmer John の $P$ 牧場のうちお気に入りの $F$ 牧場 $F_i$ を訪れるのが好きだと気付きました。番号は $1,\ldots,P$、$1\le F\le P$、$1\le P\le500$、$1\le F_i\le P$ です。
牧場を結ぶ $C$ 本の双方向の牛道（番号 $1,\ldots,C$、$1\le C\le8,000$）で、どの牧場にも行けます。道 $P_i$ の端点は $a_i,b_i$（$1\le a_i,b_i\le P$）で、どちらの方向でも所要時間は $T_i$（$1\le T_i\le892$）です。
起きた後、お気に入りの $F$ 牧場への平均移動時間が最小となる、眠るのに最適な牧場の番号を求めたいです。
下の地図の例では星印がお気に入りの牧場、角括弧の数が道の所要時間です。
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 からの距離です。
* * * * * * Favorites * * * * * *
Potential Pasture Pasture Pasture Pasture Pasture Pasture Average
Best Pasture 1 8 10 11 12 13 Distance
------------ -- -- -- -- -- -- -----------
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 ** BEST
11 13 10 1 0 3 9 36/6 = 6.00
12 16 13 4 3 0 12 48/6 = 8.00これらに最適な候補が含まれると仮定すると（プログラムでは全てを何らかの方法で調べる必要があります）、眠るのに最適なのは牧場 10 です。
入力
- 1 行目：空白区切りの $P,F,C$。
- $2,\ldots,F+1$ 行目：第 $i+2$ 行に整数 $F_i$。
- $F+2,\ldots,C+F+1$ 行目：第 $i+F+1$ 行の空白区切り $a_i,b_i,T_i$ が牛道 $i$ を表します。
出力
- 1 行に最適な牧場番号を整数で出力します。複数ある場合は最小番号を選びます。
入出力例
入力 1
13 6 15
11
13
10
12
8
1
2 4 3
7 11 3
10 11 1
4 13 3
9 10 3
2 3 2
3 5 4
5 9 2
6 7 6
5 6 1
1 2 4
4 5 3
11 12 3
6 10 1
7 8 7出力 1
10注記
問題文のとおり
問題文のとおりです。
問題作成：Rob Kolstad、2009