24134번 - スキー (Ski) 다국어

JOI 氏はスキー場として有名な IOI 高原でホテル IOI を経営している．IOI 高原はとても複雑 な地形をしておりスキー上級者にとても人気があるのだが，その複雑な地形ゆえに初心者にあ まり優しいとは言えない．しかし，JOI 氏は初心者にもこの IOI 高原の良さをわかって欲しい と思っている．

そこで最も易しいコースを見つけ出し，そのコースで IOI 高原を初心者向けに宣伝したいと 思っている．ここで言う最も易しいコースというのは平均速度 (つまり全行程の距離をかかった 時間で割って出る速度) が最も低いコースである．ただし，JOI 氏はホテル IOI を是非利用して もらいたいので，コースの始点は必ずホテル IOI から直接出ているリフトで行くことのできる 地点にし，コースの終点は必ずホテル IOI にしなければならない．

IOI 高原の各地点には標高が高いほど小さい番号が割り振られることになっている．また，標 高が同一の地点はないものとして考えて良く，高い地点からより低い地点にしか進まないと考 えて良いので，ある地点から同じ地点に戻ることはできないと考えられる．

コースとして使える道筋とその道のり，その区間平均速度およびホテル IOI からリフトで行 くことのできる地点が与えられたとき，最も易しいコースの平均速度を求め，その平均速度の 小数第一位を四捨五入した整数を出力するプログラムを作成せよ．

1行目には地点番号の最大値であるとともにホテルIOI の地点を表す正整数 n (1 ≤ n ≤ 10000) と，ホテル IOI からリフトで行くことのできる地点の数 を表す正整数 m (1 ≤ m < n)，コースとして使える道筋の本数を表す正整数 c (1 ≤ c ≤ 100000) の 3 つが空白区切りで書かれている．

2 行目にはホテル IOI からリフトで行くことのできる地点を表す正整数 a_i (1 ≤ i ≤ m, 1 ≤ a_i < n) が m 個，空白区切りで書かれている．

3 行目以降の第 j + 2 行目 (1 ≤ j ≤ c) の各行には，コースとして使うことのできる道筋の始 点の地点番号を表す正整数 f_j と終点の地点番号を表す正整数 t_j (1 ≤ f_j < t_j ≤ n)，その道筋 の始点から終点までの道のりの長さを表す正整数 d_j (1 ≤ d_j ≤ 100)，その道筋を通る場合に出 る平均速度を表す正整数 s_j (1 ≤ s_j ≤ 100000) の 4 つが空白区切りで書かれている．

採点に使われるどの入力においても，最も易しいコースの平均速度からの誤差が 0.01 以内の 値を小数第一位で四捨五入した結果は同一の整数になることが保証される．また，採点に使われるどの入力においても，ホテル IOI から直接出ているリフトで行くことのできる地点が始点 でホテル IOI が終点であるコースが存在することが保証される．

出力は標準出力に行うこと．小数第一位を四捨五入した最も易しいコースの平均速 度を整数で出力せよ．