AT_codequeen2024_final_d Attend Many Events

AtCoder Land には $ N $ 個の地点と $ M $ 個の道があります。 $ i $ 個目の道は地点 $ a_i $ と $ b_i $ を双方向に結び、通過するのに $ d_i $ 分かかります。 これから、AtCoder Land で $ K $ 個のイベントが開催されます。 $ i $ 個目のイベントに参加するには、時刻 $ t_i $ 分に地点 $ c_i $ にいる必要があります。イベントにかかる時間は $ 0 $ 分です。 あなたは、時刻 $ 0 $ 分に地点 $ 1 $ にいます。適切に行動したとき、最大で何個のイベントに参加できるか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ a_1 $ $ b_1 $ $ d_1 $ $ a_2 $ $ b_2 $ $ d_2 $ $ \vdots $ $ a_M $ $ b_M $ $ d_M $ $ c_1 $ $ t_1 $ $ c_2 $ $ t_2 $ $ \vdots $ $ c_K $ $ t_K $

答えを出力せよ。

### Sample Explanation 1 たとえば、次のように行動することで、 $ 2 $ つのイベントに参加することができます。 - はじめ、時刻 $ 0 $ 分に地点 $ 1 $ にいる - 道 $ 1 $ を通って時刻 $ 1 $ 分に地点 $ 2 $ に到着する - 時刻 $ 2 $ 分に地点 $ 2 $ でイベント $ 2 $ に参加する - 道 $ 1 $ を通って時刻 $ 3 $ 分に地点 $ 1 $ に到着する - 道 $ 2 $ を通って時刻 $ 6 $ 分に地点 $ 3 $ に到着する - 時刻 $ 7 $ 分に地点 $ 3 $ でイベント $ 3 $ に参加する $ 3 $ つ以上のイベントに参加することはできないので、答えは $ 2 $ です。 ### Sample Explanation 2 道が存在しないため、地点 $ 1 $ から動くことはできませんが、地点 $ 1 $ で開催される $ 2 $ つのイベントに参加することができます。 ### Constraints - $ 1 \leq N \leq 1000 $ - $ 0 \leq M \leq 1000 $ - $ 1 \leq K \leq 1000 $ - $ 1 \leq a_i < b_i \leq N $ - $ i \neq j $ なら $ (a_i, b_i) \neq (a_j, b_j) $ - $ 1 \leq d_i \leq 10^9 $ - $ 1 \leq c_i \leq N $ - $ 1 \leq t_i \leq 10^9 $ - $ i \neq j $ なら $ (c_i,t_i) \neq (c_j,t_j) $ - 入力はすべて整数