AT_code_festival_2018_final_h Pothunter

AtCoder 共和国由一些编号为 $1$ 到 $N$ 的城市和 $N-1$ 条编号为 $1$ 到 $N-1$ 的道路组成。每个城市通过这些道路可以相互到达。 第 $i$ 条道路连接城市 $A_i$ 和 $B_i$，通过这条路需要花费 $D_i$ 时间。 在 AtCoder 共和国中，将会有 $M$ 场现场比赛，比赛编号从 $1$ 到 $M$。 第 $i$ 场比赛在城市 $C_i$ 举行，比赛从 $S_i$ 时刻开始，到 $E_i$ 时刻结束，优胜者可以获得 $X_i$ 日元的奖金。 高桥君希望尽可能多地获取奖金。他非常强大，只要参加就能赢得所有比赛。 若高桥君要参加比赛 $i$，他必须在所有满足 $S_i \leq t < E_i$ 的时刻 $t$ 均待在城市 $C_i$，且不能同时参加其他比赛。请参照样例 1 了解详情。 假设高桥君可以在时刻 $0$ 时出现在任意一个城市，问他可以拿到的最多奖金总额是多少。

输入以以下格式给出，从标准输入读取： > $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 < 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 - 起始时刻 $0$ 时在城市 $1$ - 停留到时刻 $1$ - 然后参加时刻 $1$ 在城市 $1$ 的比赛 $1$ - 时刻 $5$ 转向城市 $2$ - 时刻 $7$ 再前往城市 $4$ - 在时刻 $8$ 参加在城市 $4$ 的比赛 $3$ - 获得的奖金总额是 $10$，此为最大值 ### 样例解释 3 - 注意，答案可能会非常大。 **本翻译由 AI 自动生成**

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