一个 \(O(n^3\log n)\) 的做法。
我们考虑枚举在环上连向外部的那个点 \(u\)，然后再在点集 \(\{1,2,\cdots u-1,u+1,\cdots n-1,n\}\) 的导出子图中跑 Floyd，枚举 \(u\) 在环上相邻的两个点 \(x,y\)，答案就是 \(d_{x,y}+w_{x,u}+w_{y,u}+\min\limits_{(u,z)\in E,z\neq x,y}w(z,u)\)。
这个样做能得到一个复杂度为 \(O(n^4)\) 的优秀算法。瓶颈在于对于每个 \(u\) 都要跑一遍 Floyd，考虑优化。
我们发现，对于一个点 \(i\)，它没被算到 Floyd 里当且仅当当前枚举的是 \(i\)，如果我们按照枚举的顺序建一个数轴，\(i\) 对 \([1,i-1]\) 和 \([i+1,n]\) 都有贡献。这启发我们线段树分治。
于是变成每次在点集中插入点，并动态维护全源最短路。事实上这很简单，插入一个点 \(u\) 时，先求出当前点集所有点到 \(u\) 的最短路，再枚举点对 \((i,j)\)，用 \(u\) 作为中转点对 \(d_{i,j}\) 更新即可。
复杂度 \(O(n^3\log n)\)。
const int N = 660;
const int inf = 1e18;
int n, m, ans = inf, w[N][N], d[N][N], f[N][3], vis[N];
vector<int> tr[N << 2];
#define ls x << 1
#define rs x << 1 | 1
#define mid ((l + r) >> 1)
void upd(int l, int r, int s, int t, int c, int x) {
if (s > t) return;
if (s <= l && r <= t) return tr[x].pb(c), void();
if (s <= mid) upd(l, mid, s, t, c, ls);
if (t > mid) upd(mid + 1, r, s, t, c, rs);
}
void dfs(int l, int r, int x) {
int t[N][N];
for (int i = 1; i <= n; i++)
memcpy(t[i], d[i], sizeof(int) * (n + 10));
for (int k : tr[x]) {
vis[k] = 1;
for (int i = 1; i <= n; i++) {
if (!vis[i]) continue;
d[i][k] = min(d[i][k], w[i][k]);
d[k][i] = min(d[k][i], w[k][i]);
}
for(int i = 1; i <= n; i++) {
if (!vis[i]) continue;
for (int j = 1; j <= n; j++) {
if (!vis[j]) continue;
d[i][k] = d[k][i] = min(d[i][k], d[i][j] + d[j][k]);
}
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) continue;
for (int j = i + 1; j <= n; j++) {
if (!vis[j]) continue;
d[i][j] = d[j][i] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
if (l != r) dfs(l, mid, ls), dfs(mid + 1, r, rs);
else if (f[l][2] != n + 1) {
for (int i = 1; i <= n; i++) {
if (i == l) continue;
for (int j = i + 1; j <= n; j++) {
if (j == l) continue;
int x = i, y = j, p;
if (w[l][x] > w[l][y]) swap(x, y);
if (x == f[l][0] && y == f[l][1]) p = f[l][2];
else if (x == f[l][0]) p = f[l][1];
else p = f[l][0];
ans = min(ans, d[i][j] + w[i][l] + w[l][j] + w[l][p]);
}
}
}
for (int i = 1; i <= n; i++)
memcpy(d[i], t[i], sizeof(int) * (n + 10));
for (int k : tr[x]) vis[k] = 0;
}
signed main() {
n = rd(), m = rd();
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
d[i][j] = w[i][j] = inf;
for (int i = 1, u, v, w; i <= m; i++) {
u = rd(), v = rd(), w = rd();
::w[u][v] = ::w[v][u] = w;
}
for (int i = 1; i <= n; i++)
w[i][i] = d[i][i] = 0;
for (int i = 1; i <= n; i++) {
f[i][0] = f[i][1] = f[i][2] = n + 1;
w[i][n + 1] = inf;
for (int j = 1; j <= n; j++) {
if (j == i) continue;
if (w[i][j] < w[i][f[i][0]]) f[i][2] = f[i][1], f[i][1] = f[i][0], f[i][0] = j;
else if (w[i][j] < w[i][f[i][1]]) f[i][2] = f[i][1], f[i][1] = j;
else if (w[i][j] < w[i][f[i][2]]) f[i][2] = j;
}
}
for (int i = 1; i <= n; i++)
upd(1, n, 1, i - 1, i, 1), upd(1, n, i + 1, n, i, 1);
dfs(1, n, 1), wr(ans < inf ? ans : -1);
return 0;
}