No.73 観光計画

時間制限:$2.0sec$ / メモリ制限:$256MB$ / tester:ei1333

問題文

kotamanegi王国には$N$個の町、$M$本の道があり、道$i$は町$a_i$と$b_i$を距離$c_i$でつないでいる。
また、$N$個の町のうち、$K$個の町にはホテルが存在しており、それぞれのホテルには快適度$d_i$が決められている。
ホテルのある町は$h_1 h_2 ... h_K$である。
olphe君はkotamanegi王国にやってきた観光客で$10^{10}$日滞在する予定である。
olphe君は毎日観光するが、以下のルールに従う。

1. olphe君は初日の夜にkotamanegi王国にやってきてどこかのホテルに宿泊する。
2. 昼間は歩いて観光するか、バスでホテル間の移動を行う。
3. 歩いて観光する場合は、前日に宿泊したホテルの快適度の距離の町まで歩いていくことができる。また、夜には前日に宿泊したホテルまで帰ってきて宿泊する。
4. バスで移動する場合には好きなホテルに移動することができる。

olphe君はできるだけ多くの町を歩いて観光したいと思っている。
olphe君が最適に行動したときに歩いて観光できる町の数を答えよ。
なお、ホテルのある町も観光することができる。

制約

• $1≦N≦10^5$
• $1≦M≦2*10^5$
• $1≦K≦N$
• $1≦a_i<b_i≦N$
• $i != j$ ならば $a_i != a_j$ もしくは $b_i != b_j$
• $1≦c_i≦10^5$
• $1≦d_i≦10^5$

入力形式

入力は以下の形式で標準入力から与えられる。

N M K
a_1 b_1 c_1
…
a_M b_M c_M
h_1 d_1
…
h_K d_K

入出力例

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

5