問題文

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 < E_i を満たすいずれの時刻 t においても町 C_i にいて他のコンテストに参加していない必要があります。 詳しくはサンプル 1 も参照してください。

高橋君が時刻 0 の時点で好きな位置にいることができるときの、高橋君が得られる賞金の総和の最大値を求めてください。

制約

• 1 \leq N,M \leq 7 \times 10^{4}
• 1 \leq A_i < B_i \leq N
• 1 \leq D_i,X_i \leq 10^{9}
• 1 \leq S_i < E_i \leq 10^{9}
• 1 \leq C_i \leq N
• 与えられる入力は全て整数
• 全ての町は道を辿って到達可能

入力例 1

5 4
1 2 2
2 3 3
2 4 1
4 5 5
1 5 1 5
2 5 3 7
8 15 4 5
12 16 5 9

出力例 1

10

• 時刻 0 に町 1 にいる
• 時刻 1 まで留まる
• 時刻 1 に町 1 で開催されるコンテスト 1 に参加する
• 時刻 5 に町 2 に向かって移動する
• 時刻 7 に町 4 に向かって移動する
• 時刻 8 に町 4 で開催されるコンテスト 3 に参加する
• 得られる賞金の総和は 10 となり、これが最大です

入力例 2

11 10
5 9 1
2 9 5
4 8 4
2 6 1
3 7 3
5 8 2
2 11 5
3 11 1
1 4 3
9 10 3
1 7 11 10
2 8 9 12
8 15 3 11
2 3 2 4
3 6 4 6
7 9 5 9
4 8 1 7
11 18 6 9
10 14 6 4
5 11 7 11

出力例 2

21

入力例 3

2 6
1 2 1000000000
1 2 1 1000000000
3 4 1 1000000000
5 6 1 1000000000
7 8 1 1000000000
899999999 900000000 1 1000000000
999999999 1000000000 2 1000000000

出力例 3

5000000000

• 答えは非常に大きくなりうることに注意してください