在罗马尼亚，Zacuscă 是一种蔬菜酱，通常由烤茄子和辣椒制成，不过也可以加入洋葱、西红柿、油和香料。

制作 Zacuscă 需要准备好原料并将它们混合在一起。你已经准备好了原料，现在是混合的时候了。你首先将第一种原料放入搅拌机中。然后加入第二种，接着是第三种，依此类推。每一次加入，混合物都会变得更难搅拌。具体来说，有 $M$ 个形如 $(i, j, a, b)$ 的关系。这意味着，如果你将原料 $j$ 加入到已经含有另一种原料 $i$ 的混合物中，搅拌机将消耗 $a$ 单位的额外能量。类似地，如果你将原料 $i$ 加入到已经含有原料 $j$ 的混合物中，搅拌机将消耗 $b$ 单位的额外能量。

在本题中，假设无论你以何种顺序加入原料，最终的混合物都是相同的（在实际烹饪中并非如此）。由于你需要制作相当多的 Zacuscă，你希望找到最有效的配方：即混合所有原料所需能量最少的配方。输出所需的最小能量。

输入格式

第一行包含两个整数 $n$ 和 $m$：原料的数量和能量关系的数量（$2 \le n \le 24, 1 \le m \le \frac{n(n-1)}{2}$）。

接下来的 $m$ 行，每行包含四个整数：$i, j, a$ 和 $b$（$1 \le i, j \le n, i \neq j, 1 \le a, b \le 10^6$）。没有任意一对 $(i, j)$ 会出现多次。对 $(i, j)$ 和 $(j, i)$ 不会同时出现。

输出格式

输出一个整数，表示混合所有原料所需的最小能量。

样例

输入样例 1

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

输出样例 1

12

说明

在样例中，我们可以选择按照 $3, 1, 2$ 的顺序加入这三种原料，这将产生以下花费：

• 在已含有 $1$ 的情况下加入 $2$ 花费 $3$
• 在已含有 $3$ 的情况下加入 $1$ 花费 $3$
• 在已含有 $3$ 的情况下加入 $2$ 花费 $6$

因此总花费为 $12$，并且没有其他顺序能带来更小的花费。