Problem Description

You are given a connected undirected weighted graph. For each edge $i$, based on its original weight, increasing its weight by $1$ costs $a_i$, and decreasing its weight by $1$ costs $b_i$.

Now a spanning tree of the graph is specified. Find the minimum total cost needed to modify edge weights so that this spanning tree becomes a minimum spanning tree of the graph.

Input Format

The first line contains two positive integers $n, m$, representing the number of vertices and edges in the graph. The vertices are numbered from $1$ to $n$.

The next $m$ lines each contain $6$ positive integers $u_i, v_i, w_i, \textit{ff}_i, a_i, b_i$, describing an edge $(u_i, v_i)$ with weight $w_i$. Increasing the original weight by $1$ costs $a_i$, and decreasing the original weight by $1$ costs $b_i$. If $\textit{ff}_i$ is $1$, the edge is in the specified spanning tree; if $\textit{ff}_i$ is $0$, it is not. The data guarantees that the edges with $\textit{ff}_i = 1$ form exactly a spanning tree of the original graph. There may be multiple different edges between two vertices, but there are no self-loops.

Output Format

Output a positive integer, the minimum total cost required.

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

21

Hint

Sample Explanation

The optimal plan is:

• Increase the weight of edge $(1,4)$ by $2$, cost $6$.
• Increase the weight of edge $(3,5)$ by $3$, cost $3$.
• Increase the weight of edge $(3,6)$ by $4$, cost $8$.
• Decrease the weight of edge $(4,5)$ by $2$, cost $4$.

The total cost is $21$.

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 300$, $1 \leq m, w_i, a_i, b_i \leq 1000$.

Translated by ChatGPT 5