CF21D Traveling Graph

给定一个带权无向图，找到一个权值最小的环，从起点 $1$ 开始，至少遍历图上的每一条边各一次，最后回到 $1$ 点。图可能有重边与自环。

输入第一行有两个整数 $n,m$，表示给定图的边数与点数。保证 $1\le n\le 15,0\le m\le 2000$。 接下来 $m$ 行每行 $3$ 个整数 $x,y,w$ 描述一条边。其中 $x,y$ 表示边的两个端点，$w$ 表示边权。保证 $1\le x,y\le n,1\le w\le 10000$。

一行一个整数，表示权值最小的环的权值。如果不存在这样的环，输出 $-1$。

数据范围： - $1\le x,y\le n\le 15$； - $0\le m \le 2500$； - $1\le w \le 10000$。