MinDAG

Task

An undirected graph with $N$ nodes and $M$ edges is given.

Each edge $(i, j)$ is assigned two costs, $a$ and $b$. It can be directed from $i$ to $j$ with a cost of $a$, or from $j$ to $i$ with a cost of $b$.

Choose a direction for each edge such that the resulting directed graph is acyclic and the sum of the costs is minimized.

Input data

The first line of the input contains two integers, $N$ and $M$, representing the number of nodes and the number of edges in the graph.

The next $M$ lines each contain four integers, $i$, $j$, $a$, and $b$, indicating that there is an edge between nodes $i$ and $j$ with the properties described above.

Output data

The first line contains the integer $C$, representing the required minimum cost.

Constraints and clarifications

• $1 \leq N \leq 24$
• $1 \leq M \leq \frac{N * (N - 1)}{2}$
• $1 \leq a, b \leq 10^6$
• $1 \leq i, j \leq N$
• The input edges do not repeat.

Example

stdin

3 3
1 2 3 5
1 3 7 3
2 3 5 6

stdout

12

Explanation

The edges can be oriented as follows:

• $1 \rightarrow 2$ with a cost of $3$
• $3 \rightarrow 1$ with a cost of $3$
• $3 \rightarrow 2$ with a cost of $6$