問題文

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$
• 与えられる入力は全て整数
• 全ての町は道を辿って到達可能

入力

入力は以下の形式で標準入力から与えられる。

$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

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

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