AT_past202104_g 一日一歩

[problemUrl]: https://atcoder.jp/contests/past202104-open/tasks/past202104_g ある国には都市 $ 1 $ から都市 $ N $ までの $ N $ 個の都市と、道 $ 1 $ から道 $ M $ までの $ M $ 本の道があります。 道 $ i $ は都市 $ A_i $ と都市 $ B_i $ を双方向に繋ぎ、$ C_i $ 単位時間で通行することができます。 現在都市 $ 1 $ にいるあなたは $ Q $ 日間にわたる旅をします。開始から $ i $ 日目の昼には以下のどちらかの行動を行います。 - 何もしない - 今いる都市に繋がっている道を $ 1 $ つ選び、その道の先の都市に移動する。このとき選ぶ道は $ X_i $ 単位時間以下で通行できるものでなければならない。 $ 1 $ 以上 $ Q $ 以下の各整数 $ i $ について、開始から $ i $ 日目の夕方にあなたがいる可能性のある都市の数を求めてください。 $ 1 $ 単位時間は $ 1 $ 日の $ \frac{1}{10^{100}} $ より短いものとします。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ A_1 $ $ B_1 $ $ C_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ A_3 $ $ B_3 $ $ C_3 $ $ \hspace{25pt}\ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ X_1 $ $ X_2 $ $ X_3 $ $ \dots $ $ X_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、開始から $ i $ 日目の夕方にあなたがいる可能性のある都市の数を出力せよ。

### 注意 この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - $ 2\ \le\ N\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ M\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ Q\ \le\ 2\ \times\ 10^5 $ - $ 1\ \le\ A_i\