問題文

AtCoder Land には N 個の地点と M 個の道があります。i 個目の道は地点 a_i と b_i を双方向に結び、通過するのに d_i 分かかります。

これから、AtCoder Land で K 個のイベントが開催されます。i 個目のイベントに参加するには、時刻 t_i 分に地点 c_i にいる必要があります。イベントにかかる時間は 0 分です。

あなたは、時刻 0 分に地点 1 にいます。適切に行動したとき、最大で何個のイベントに参加できるか求めてください。

制約

• 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)
• 入力はすべて整数

入力例 1

3 3 3
1 2 1
1 3 3
2 3 7
1 8
2 2
3 7

出力例 1

2

たとえば、次のように行動することで、2 つのイベントに参加することができます。

• はじめ、時刻 0 分に地点 1 にいる
• 道 1 を通って時刻 1 分に地点 2 に到着する
• 時刻 2 分に地点 2 でイベント 2 に参加する
• 道 1 を通って時刻 3 分に地点 1 に到着する
• 道 2 を通って時刻 6 分に地点 3 に到着する
• 時刻 7 分に地点 3 でイベント 3 に参加する

3 つ以上のイベントに参加することはできないので、答えは 2 です。

入力例 2

1 0 2
1 1
1 100

出力例 2

2

道が存在しないため、地点 1 から動くことはできませんが、地点 1 で開催される 2 つのイベントに参加することができます。

入力例 3

5 8 10
1 2 149622151
1 4 177783960
4 5 118947237
1 3 33222944
1 5 295060863
3 5 110881471
2 3 34104208
3 4 273071547
2 650287940
4 839296263
3 462224593
1 492601449
4 384836991
1 191890310
5 576823355
3 782177068
3 404011431
1 818008580

出力例 3

6