Description

As the saying goes, you reap what you sow. MloVtry cut off half of itself and buried it in the ground, and thus obtained a “Salted Fish Tree” with $n$ vertices.

However, because MloVtry only buried half of itself, this Salted Fish Tree is incomplete — it has even broken into $m$ edges.

As a salted fish that could cause cancer, MloVtry certainly wants a Salted Fish Tree to show its identity.

MloVtry has roughly estimated the cost of connecting two vertices and wants to know the minimum total cost needed to assemble a Salted Fish Tree.

Note that the edges on the Salted Fish Tree have strong opinions about MloVtry. Each edge specifies a vertex set $S$. Only after MloVtry has connected all vertices in this special set $S$ into some set $T$ can this edge be added to that set $T$.

MloVtry buried its brain in the ground, so you have to solve this problem.

Input Format

The first line contains $2$ integers $n, m$.

The next $m$ lines each contain $4$ integers $u, v, S, l$, denoting an undirected edge of length $l$ between $u$ and $v$, which can only be chosen after the vertex set $S$ has already been selected (this set is represented by a binary number; vertex $1$ corresponds to the first bit, and so on).

Output Format

Output a single integer, the minimum total cost. If there is no solution, output $-1$.

2 7
1 2 1 14
2 1 2 11
2 2 1 18
2 1 2 16
2 1 2 12
2 1 2 16
2 1 3 13

11

Hint

Constraints: $1 \le n \le 15$, $1 \le m \le n \times (n+10)$.

The testdata guarantees that all values are within the range of a 32-bit int.

Translated by ChatGPT 5