AT_code_festival_2018_final_h Pothunter

[problemUrl]: https://atcoder.jp/contests/code-festival-2018-final/tasks/code_festival_2018_final_h AtCoder共和国は $ 1 $ から $ N $ までの番号がついた町と $ 1 $ から $ N-1 $ の番号がついた $ N-1 $ 本の道からできています。それぞれの町は道をたどって到達可能です。 道 $ i $ は町 $ A_i $ と $ B_i $ を双方向につなぐ道で、移動に $ D_i $ だけ時間がかかります。 AtCoder共和国で $ 1 $ から $ M $ までの番号がついた $ M $ 個のオンサイトコンテストが開催されることになりました。 コンテスト $ i $ は町 $ C_i $ で開催され、開始時刻は $ S_i $ で終了時刻は $ E_i $ です。また、コンテストの優勝賞金は $ X_i $ 円です。 賞金稼ぎの高橋君は、賞金をできる限りたくさんもらいたいです。高橋君はとても強いので参加したコンテスト全てで優勝可能です。 高橋君がコンテスト $ i $ に参加するためには、$ S_i\ \leq\ t\

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ D_1 $ $ : $ $ A_{N-1} $ $ B_{N-1} $ $ D_{N-1} $ $ S_1 $ $ E_1 $ $ C_1 $ $ X_1 $ $ : $ $ S_{M} $ $ E_{M} $ $ C_{M} $ $ X_{M} $

答えを出力せよ。

### 制約 - $ 1\ \leq\ N,M\ \leq\ 7\ \times\ 10^{4} $ - $ 1\ \leq\ A_i\