问题描述

高桥君所居住的城市中有 $N$ 个房屋和 $M$ 条道路。房屋用整数 $1$ 到 $N$ 进行编号。高桥君居住在第一个房屋。道路也用整数 $1$ 到 $M$ 进行编号。第 $i$ 条道路是一条连接房屋 $u_i$ 和房屋 $v_i$ 的双向道路，长度为 $l_i$ 米。

高桥君正在寻找一只名为 "幸福的蓝鸟" 的鸟。事实上，"幸福的蓝鸟" 就在高桥君的家里，高桥君也知道这件事。然而，为了增加乐趣，他决定制定一项旅行计划。

高桥君计划从自己的家出发，依次访问一些房屋，但不能经过同一条道路两次，并最终回到自己的家。此外，为了增加乐趣，他计划在旅途中至少访问除自己的家之外的一座房屋。高桥君希望尽快完成这个闹剧，因此他认为通过的道路长度之和最小的计划是最优的。

给定高桥君所在的城市的房屋和道路信息，请判断高桥君是否可以制定最优计划，并计算在此情况下通过的道路长度之和。

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $u_1$ $v_1$ $l_1$ $u_2$ $v_2$ $l_2$ : $u_M$ $v_M$ $l_M$

• 第 $1$ 行为高桥君所在城市的房屋数量 $N(3≤N≤300)$ 和道路数量 $M(3≤M≤N(N-1)/2)$，以空格分隔。
• 接下来的 $M$ 行，每行描述一条道路。第 $i$ 行描述编号为 $i$ 的道路连接的两个房屋编号 $u_i, v_i(1≤u_i < v_i ≤ N)$ 和该道路的长度 $l_i(1≤l_i≤10^5)$，以空格分隔。
• 对于任意 $i ≠ j$，要么 $u_i ≠ u_j$，要么 $v_i ≠ v_j$。

输出

如果无法制定最优计划，则输出 $-1$；否则，输出通过的道路长度之和，并在末尾加上换行符。

输入示例1

5 7
1 2 2
1 4 1
2 3 7
1 5 12
3 5 2
2 5 3
3 4 5

输出示例1

13

房屋和道路的示意图如下所示：

计划按照 $1, 2, 5, 3, 4, 1$ 的顺序访问各个房屋时，通过的道路长度之和最小。如果按照 $1, 2, 1$ 的顺序访问各个房屋，则会经过第一条道路两次，不满足要求。

输入示例2

5 4
1 2 1
1 3 1
1 4 1
1 5 1

输出示例2

-1

不能制定一个不经过同一条道路两次的旅行计划，因此输出 $-1$。

输入示例3

10 12
1 4 3
1 9 1
2 5 4
2 6 1
3 7 5
3 10 9
4 7 2
5 6 6
5 8 5
6 8 3
7 9 5
8 10 8

输出示例3

11