考虑枚举唯一一个度数为 \(3\) 的点 \(u\)，即既在环上又与非环上一点相连的那个点。
接下来考虑先处理环，那可以先把 \(u\) 从图上删掉，环的最短距离便是与 \(u\) 有连边的 \(2\) 个点在图上最短路长度加上 \(2\) 个点与 \(u\) 连边的长度，即 \(\min\{w_{u, i} + w_{u, j} + \operatorname{dis}(i, j)\}((u, i), (u, j)\in E)\)（\(w_{u, v}\) 代表 \((u, v)\) 这条边的长度，\(\operatorname{dis}(u, v)\) 代表 \((u, v)\) 在图中的最短路）。
但是发现 \(i, j\) 不能枚举直接跑最短路也不妥，考虑怎么处理。
因为 \(i, j\) 不同所以 \(i, j\) 二进制肯定至少 \(1\) 位不同，那就可以枚举二进制位 \(x\) 了，把编号二进制第 \(x\) 位为 \(1\) 的点当作起点，编号二进制第 \(x\) 位为 \(0\) 的点当作终点跑，这样能保证每个环都能跑到。
然后就可以处理单独的那一条边了，找到这个环与 \(u\) 相连的点 \(i, j\)，这部分答案即为 \(\min\{w_{u, k}\}(k\not ={i}, k\not ={j}, (u, k)\in E)\)。
但是注意可能会有更优的解：
\((u, x)\) 或 \((u, y)\) 为单独的边，剩下部分再跑出一个环两部分总和。
所以再删除 \(x\) 或删除 \(y\) 然后同样方法跑图上的最短环加上这条边的长度即可。
使用朴素 \(\text{Dijkstra}\) 跑最短路，时间复杂度 \(O(n^3\log_2 n)\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: Ex - Make Q
// Contest: AtCoder - AtCoder Beginner Contest 308
// URL: https://atcoder.jp/contests/abc308/tasks/abc308_h
// Memory Limit: 1024 MB
// Time Limit: 4000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
const int N = 3e2 + 10;
const int inf = 0x3f3f3f3f;
int w[N][N], p[N][N];
int hd[N], ltot;
int n;
int z[N], dis[N], vis[N], lst[N];
int dij(int u, int &x, int &y) {
for (int i = 1; i <= n; i++) {
dis[i] = inf, vis[i] = 0, lst[i] = 0;
}
for (int i = 1; i <= n; i++) {
if (z[i] && w[u][i] < inf) {
dis[i] = w[u][i];
}
}
for (; ; ) {
int mx = inf, mxu;
for (int i = 1; i <= n; i++) {
if (dis[i] < mx && ! vis[i]) {
mx = dis[i], mxu = i;
}
}
if (mx == inf) {
break;
}
vis[mxu] = 1;
for (int v = 1; v <= n; v++) {
if (mx + p[mxu][v] < dis[v]) {
dis[v] = mx + p[mxu][v], lst[v] = mxu;
}
}
}
int val = inf;
for (int i = 1; i <= n; i++) {
if ((! z[i]) && dis[i] + w[u][i] < val) {
val = dis[i] + w[u][i], y = i;
}
}
if (val == inf) {
return inf;
}
for (x = y; lst[x]; x = lst[x]);
return val;
}
int _solve(int u, int &a, int &b) {
int ans = inf;
for (int i = 0; (1 << i) <= n; i++) {
for (int j = 1; j <= n; j++) {
z[j] = (j >> i) & 1;
}
int x, y;
int val = dij(u, x, y);
if (val < ans) {
ans = val, a = x, b = y;
}
}
return ans;
}
int solve(int u) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
p[i][j] = ((i == u || j == u) ? inf : w[i][j]);
}
}
int lv = 0;
for (int i = 1; i <= n; i++) {
if (w[u][i] < inf) {
lv++;
}
}
if (lv < 3) {
return inf;
}
int ans = inf;
int a, b;
int s = _solve(u, a, b);
if (s == inf) {
return inf;
}
for (int i = 1; i <= n; i++) {
if (i != a && i != b && s + w[u][i] < ans) {
ans = s + w[u][i];
}
}
int x, y;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
p[i][j] = ((i == u || j == u || i == a || j == a) ? inf : w[i][j]);
}
}
ans = min(ans, _solve(u, x, y) + w[u][a]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
p[i][j] = ((i == u || j == u || i == b || j == b) ? inf : w[i][j]);
}
}
ans = min(ans, _solve(u, x, y) + w[u][b]);
return ans;
}
int main() {
int m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = inf;
}
}
for (int i = 1; i <= m; i++) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
w[x][y] = w[y][x] = z;
}
int ans = inf;
for (int i = 1; i <= n; i++) {
ans = min(ans, solve(i));
}
printf("%d\n", ans == inf ? -1 : ans);
return 0;
}