题目描述
Problem Description
The Republic of AtCoder consists of towns numbered from $1$ to $N$ and $N-1$ roads numbered from $1$ to $N-1$. Each town is reachable by following the roads.
Road $i$ connects town $A_i$ and $B_i$ bidirectionally, and it takes $D_i$ time to travel.
$M$ onsite contests numbered from $1$ to $M$ will be held in the Republic of AtCoder.
Contest $i$ is held in town $C_i$, starting at time $S_i$ and ending at time $E_i$. The winning prize for the contest is $X_i$ yen.
Takahashi, a prize hunter, wants to collect as much prize money as possible. Takahashi is very strong and can win every contest he participates in.
To participate in contest $i$, Takahashi must be in town $C_i$ at any time $t$ that satisfies $S_i \leq t < E_i$ and not participating in any other contest. Refer to Sample $1$ for more details.
Given that Takahashi can be at any position at time $0$, find the maximum total prize money he can obtain.
Input Format
The input is given from the standard input in the following format:
$ 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} $
Output Format
Output the answer.
Sample Input and Output
Sample Input #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
Sample Output #1
10
Sample Input #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
Sample Output #2
21
Sample Input #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
Sample Output #3
5000000000
Notes/Hints
Constraints
- $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$
- All given inputs are integers
- All towns are reachable by following the roads
Sample Explanation 1
- Stay in town $1$ until time $1$
- Participate in contest $1$ held in town $1$ at time $1$
- Move to town $2$ at time $5$
- Move to town $4$ at time $7$
- Participate in contest $3$ held in town $4$ at time $8$
- The total prize money obtained is $10$, which is the maximum
Sample Explanation 3
- Note that the answer can be very large
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分