MloVtry的咸鱼树

题目背景

签到~

题目描述

俗话说种瓜得瓜,种豆得豆,MloVtry 把自己砍掉一半埋进了土里,于是它得到了一颗 $n$ 个点的咸鱼树。 但是问题是由于 MloVtry 只舍得埋下一半的自己,所以这个咸鱼树是不完整的---甚至它碎裂成了 $m$ 条边。 作为一条能够致癌的咸鱼,MloVtry 当然想要一颗咸鱼树来标榜自己的身份。 MloVtry 大概估计出了连接两个点之间的代价,它想知道,最少需要多少代价才能拼出咸鱼树? 值得注意的是,咸鱼树上的咸鱼边们对于 MloVtry 是很有意见的,所以每条边都会制定一个点集 $S$,只有 MloVtry 将 $S$ 这个特殊点集里的所有点都接入某个集合 $T$ 之后,这条边才可以被加入 $T$ 这个集合。 MloVtry 把脑子埋进了地里,所以这个问题只能由你来解决了。

输入输出格式

输入格式


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

输出格式


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

输出样例 #1

11

说明

$1\le n\le 15$,$1\le m\le n\times (n+10)$。 数据保证所有数值在 int 范围内。