给你一个无向加权图。求从顶点 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