← 返回题目列表

Codeforces · 21/D

D. 旅行图

中文机器翻译题面 查看原题

给你一个无向加权图。求从顶点 1 开始并经过所有边至少一次的最短循环的长度。图可能包含一对顶点和循环之间的多条边(从顶点到自身的边)。

输入

输入的第一行包含两个整数n和m(1 ≤ n ≤ 15, 0 ≤ m ≤ 2000),n是顶点数量,m是边数量。以下 m 行包含作为三元组 x、y、w 的边(1 ≤ x、y ≤ n、1 ≤ w ≤ 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