P4854 MloVtry’s Salted Fish Tree

Sign-in~.

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.

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 a single integer, the minimum total cost. If there is no solution, output $-1$.

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