Description

Farmer John 有 N 个农场，编号为 1 ~ N。

有 M 条双向通行的道路。每条道路连接两个不同的农场。两个农场之间可能有多条道路。每条道路的长度是已知的。

奶牛 Bessie 想要找一条环形跑路线，使得路线上至少包含三个农场，且中途不能重复经过同一个农场。

Bessie 希望这样的环形跑路线最短，你能帮助她吗？

Input

多组数据，不超过 3 组。对于每组数据：

• 第一行：两个整数 N 和 M
• 接下来的 M 行：每行三个整数 u, v, w，表示 u 和 v 之间有一条长度为 w 的道路

Output

每组数据的答案占一行：输出最短的环形跑路线的长度；如果找不到满足条件的路线，输出 -1

Sample Input

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

Sample Output

12
-1

Data Size

N ≤ 300, M ≤ 30000, 1 ≤ u, v ≤ N, 0 ≤ w ≤ 10^9