问题文

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

• 注意答案可能非常大