D. 旅行图

每个测试点的时间限制：0.5 秒
内存限制：64 MB

你有一张无向带权图。请找出从顶点 $1$ 出发，且经过所有边至少一次的最短环的长度。图中可能包含两个顶点之间的多条边，以及自环（从顶点到自身的边）。

输入格式
第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 15$，$0 \le m \le 2000$），$n$ 是顶点数量，$m$ 是边的数量。
接下来的 $m$ 行，每行包含三个整数 $x, y, w$（$1 \le x, y \le n$，$1 \le w \le 10000$），$x, y$ 是边的两个端点，$w$ 是边的长度。

输出格式
输出最短环的长度，如果不存在则输出 $-1$。

示例

输入 #1

3 3
1 2 1
2 3 1
3 1 1

输出 #1

3

输入 #2

3 2
1 2 3
2 3 4

输出 #2

14