题目描述

A 国有 $n$ 个城市被 $n-1$ 条道路连接！这 $n$ 座城市从 $1$ 至 $n$ 编号，其中第 $i$ 座城市有三个值 $A_i$、$B_i$ 以及 $C_i$ 分别表示该城市的繁荣度、利润额和销售额。

你作为一个流浪商人，想要进行环游 A 国的 $m$ 次旅行。第 $i$ 次旅行可以描述为：以 $X$ 元的资金从城市 $S_i$ 以最短距离走到城市 $T_i$，且最终资本需要大于等于 $Y_i$，还有一个参数 $K_i$。你一路破产，一路贸易，一路生花。

• 一路破产：你需要最开始携带 $X$ 元的资金，从城市 $S_i$ 开始出发。
• 一路贸易：你在途经的所有城市都需要进行贸易，包括出发城市和结束城市。 假设你刚来到城市 $i$ 拥有资金 $w$ 元，若资本 $w$ 不小于该城市的繁荣度 $A_i$，那么你可以在此获利 $B_i$。否则你会消耗 $C_i$ 元的资金。路途中资金可以小于 $0$。
• 一路生花：抵达城市 $T_i$ 并在城市 $T_i$ 完成贸易后，你希望最后至少有 $Y_i$ 元的资金，且在路途中至少完成 $K_i$ 次获利（即至少有 $K_i$ 个城市满足当前资本不小于该城市的繁荣度 $A_i$）。$Y_i$ 可以小于 $X$，因为你深知破产无关紧要，绕远的路，总有风景。

你需计算 $X$ 的最小值，使得每次旅行都以 $X$ 元资金出发，且最后都至少有 $Y_i$ 元的剩余且获利至少 $K_i$ 次。保证 $K_i$ 小于等于路径长度。

输入格式

第一行两个整数 $n,m$，分别表示城市数量和旅行次数。

第二行至第 $n$ 行，每行两个整数 $u,v$，表示 A 国的道路。

接下来有 $n$ 行，每行有三个整数 $A_i,B_i,C_i$，表示第 $i$ 个城市的繁荣度、利润额和销售额。

接下来有 $m$ 行，每行有三个整数 $S_i,T_i,Y_i,K_i$，表示第 $i$ 次旅行从 $S_i$ 出发，$T_i$ 结束，且要求最终资金需要大于等于 $Y_i$，获利次数大于等于 $K_i$。

输出格式

输出一行一个整数 $X$ 表示最小的初始资金。

3 3
2 1
3 1
3 9 0
5 5 0
7 6 7
3 2 4 2
2 1 8 1
3 1 4 1

7

4 5
2 1
3 1
4 3
1 8 5
7 8 6
1 9 2
1 8 0
1 4 8 1
3 2 7 2
3 4 3 1
2 3 9 2
2 4 7 1

7

提示

【数据规模与约定】

本题开启子任务捆绑测试。本题自动开启 O2 优化。

• Subtask 1（10 pts）：$n\leq 100$，$m\leq 100$。
• Subtask 2（25 pts）：$n\leq 500$，$m\leq 3000$。
• Subtask 3（10 pts）：$A_i=B_i$，$C_i=0$。
• Subtask 4（10 pts）：$B_i=0$。
• Subtask 5（10 pts）：$C_i=0$。
• Subtask 6（10 pts）：A 国的道路是一条链。
• Subtask 7（25 pts）：$n\leq 500$，$m\leq 2\times 10^5$。

对于所有测试点满足 $n\leq 500$，$m\leq 2\times 10^5$，$0\leq A_i,B_i,C_i\leq 2\times 10^{14}$，$S_i\not= T_i$，$1\leq K_i\leq n$，$1\leq Y_i\leq 10^{17}$。