CF21D.Traveling Graph

You are given undirected weighted graph. Find the length of the shortest cycle which starts from the vertex 1 and passes throught all the edges at least once. Graph may contain multiply edges between a pair of vertices and loops (edges from the vertex to itself).

给你一个无向带权图。请找出从顶点 1 出发、且至少经过每条边一次的最短环路的长度。该图中可能存在一对顶点之间的多条边（重边）以及自环（即从某个顶点指向其自身的边）。

The first line of the input contains two integers n and m (1 ≤ n ≤ 15, 0 ≤ m ≤ 2000), n is the amount of vertices, and m is the amount of edges. Following m lines contain edges as a triples x, y, w (1 ≤ x, y ≤ n, 1 ≤ w ≤ 10000), x, y are edge endpoints, and w is the edge length.

输入的第一行包含两个整数 $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$ 是该边的长度。

Output minimal cycle length or -1 if it doesn't exists.

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