Link with Railway Company

题号：NC254986
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

Link is the owner of a railway company. The railway company currently operates $n$ stations and $m$ railway lines.

The railway network consists of $n-1$ bidirectional railways, and any two stations can be reached from each other through the railway network. The railways in the network can be represented by $n-1$ triplets $(u_i, v_i, c_i)$ , where $u_i$ and $v_i$ are the starting and ending stations of the railway, and $c_i$ is the daily maintenance cost for that railway.

The operated transport lines of the company can be represented by $m$ quadruplets $(a_i, b_i, x_i, y_i)$ . Here, $a_i$ and $b_i$ are the starting and ending stations of the line, $x_i$ represents the daily revenue generated by the line, and $y_i$ represents the additional expenses incurred by operating this line daily.

The company is currently undergoing a reform: abandoning some underperforming lines and stopping maintenance on certain railways to improve the company's profitability.

Link wants to know, in the optimal state, what is the maximum daily revenue the company can achieve after the reform?

输入描述:

The first line contains two integers,  and  .

The next  lines contain three integers each, , , and  , representing a railway.

The next  lines contain four integers each, , , , and  , representing a transport line operated by the company.

It is guaranteed that any two stations can be reached from each other through the railway network.

输出描述:

Output a single integer on a line, representing the maximum daily revenue.

示例1

输入

复制

输出

复制