配点 : 900 点
問題文
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
- 请注意,答案可能非常大 编号至