旅行图AI (CI翻译)
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 出发、至少经过每条边一次并最终回到顶点 1 的最短环的长度。图中一对顶点之间可能存在重边，也可能存在环（即连接某个顶点与其自身的边）。AI (CI翻译)
Input
输入格式
AI (CI翻译)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 ≤ *n* ≤ 15, 0 ≤ *m* ≤ 2000$），其中 $*n*$ 表示顶点数，$*m*$ 表示边数。接下来的 $*m*$ 行每行包含一条边的信息，以三个整数 $*x*, *y*, *w*$ 表示（$1 ≤ *x*, *y* ≤ *n*, 1 ≤ *w* ≤ 10000$），其中 $*x*$ 和 $*y*$ 是边的两个端点，$*w*$ 是边的长度。AI (CI翻译)
Output
输出格式
AI (CI翻译)Output minimal cycle length or -1 if it doesn't exists.
输出最短环的长度。如果不存在这样的环，则输出 -1。AI (CI翻译)
样例
3 3
1 2 1
2 3 1
3 1 1
3
3 2
1 2 3
2 3 4
14
题面与样例版权归 Codeforces 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。