Description

俗话说种瓜得瓜，种豆得豆，MloVtry 把自己砍掉一半埋进了土里，于是它得到了一颗 $n$ 个点的咸鱼树。

但是问题是由于 MloVtry 只舍得埋下一半的自己，所以这个咸鱼树是不完整的---甚至它碎裂成了 $m$ 条边。

作为一条能够致癌的咸鱼，MloVtry 当然想要一颗咸鱼树来标榜自己的身份。

MloVtry 大概估计出了连接两个点之间的代价，它想知道，最少需要多少代价才能拼出咸鱼树？

值得注意的是，咸鱼树上的咸鱼边们对于 MloVtry 是很有意见的，所以每条边都会制定一个点集 $S$，只有 MloVtry 将 $S$ 这个特殊点集里的所有点都接入某个集合 $T$ 之后，这条边才可以被加入 $T$ 这个集合。

MloVtry 把脑子埋进了地里，所以这个问题只能由你来解决了。

Input Format

第一行 $2$ 个整数 $n,m$。

接下来 $m$ 行，每行 $4$ 个整数 $u,v,S,l$，表示一条连接 $u$ 到 $v$ 的长为 $l$ 的双向边，要在已经选择了点集 $S$（这个集合用二进制数来表示，$1$ 号点对应第 $1$ 位，其余点同理）之后才能选择。

Output Format

一行 $1$ 个整数，表示最小代价。当然，可能存在无解的情况，此时请输出 $-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

$1\le n\le 15$，$1\le m\le n\times (n+10)$。

数据保证所有数值在 int 范围内。