黒く塗った辺のうちサイクルに含まれない唯一の辺（これを飛び出た辺とよぶ）が結ぶ \(2\) つの頂点のうち、サイクルに含まれる方の頂点を \(a\) とします。サイクルにおいて頂点 \(a\) に隣接する \(2\) つの頂点を \(b,c\) とします。飛び出た辺が結ぶ \(2\) つの頂点のうち \(a\) でない方を \(d\) とします。元の条件では \(d\) はサイクルに含まれない必要がありますが、実際のところ、\(d \neq b\) かつ \(d \neq c\) が唯一の条件であるとして答えを求めても問題ありません（\(a,b,c\) 以外でサイクルに含まれる頂点と \(d\) が一致するとき、黒く塗られた辺のいくつかを白く塗れば Q を作れるためです）。

\(a\) を全探索します（以下、 \(a\) を固定して考えます）。まず、頂点 \(a\) を含むサイクルのうち、含まれる辺の総コストが最小であるものを \(O(N^2)\) で求めます。求め方は yukicoder No.1320 などで説明されていますが、簡潔には以下の通りです。

• 頂点 \(a\) を根とする最短路木 \(T\) を構築する。
• 各頂点 \(j\) について、ラベル \(L_j\) を以下のように定める：
  • \(j=a\) のとき、\(L_j=a\)
  • \(j \neq a\) のとき、\(T\) 上で頂点 \(j\) の祖先（\(j\) を含む）かつ頂点 \(a\) の子である唯一の頂点を \(x\) として、\(L_j = x\)
• \(L_{A_i} \neq L_{B_i}\) を満たす各 \(i\) について、「\(T\) 上での \(a-A_i\) パス」「\(T\) 上での \(a-B_i\) パス」「辺 \(i\)」をつなげてできるサイクルを \(\text{cycle}_i\) とする。\(\text{cycle}_i\) のうち含まれる辺の総コストが最小であるものが求めるサイクルである。

正当性は、\(L_{A_i} \neq L_{B_i}\) を満たす辺 \(i\) がかならず \(1\) つ以上サイクルに含まれること、\(T\) が最短路木であることから示せます。

今求めたこのサイクルが作った Q に含まれるとき、飛び出た辺としては、「頂点 \(a\) に繋がる辺のうちもう一方の端点が \(b\) でも \(c\) でもないもの」のうちコストが最小であるもののを選ぶのが明らかに最適です。あとは「頂点 \(a,b\) を結ぶ辺」や「頂点 \(a,c\) を結ぶ辺」が飛び出た辺である場合をそれぞれ考慮すればよいですが、これは、それぞれの辺を一旦グラフから削除した上で上述の最小サイクルを求めるアルゴリズムをもう一度行うことで求められます。

よってこの問題を \(O(N^3)\) で解くことができました。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

const int inf = 1e8;

pair<int, vector<int>> shortest_cycle(const vector<vector<int>> &G, int r) {
    int n = G.size();
    vector<int> dist(n, inf * 2), p(n, -1), g(n);
    vector<bool> seen(n);
    dist[r] = 0;
    g[r] = r;
    for (int t = 0; t < n; t++) {
        int mn = inf * 2, pos = -1;
        for (int i = 0; i < n; i++) {
            if (!seen[i] and dist[i] < mn) {
                mn = dist[i];
                pos = i;
            }
        }
        assert(pos != -1);
        seen[pos] = true;
        for (int i = 0; i < n; i++) {
            if (dist[i] > dist[pos] + G[pos][i]) {
                dist[i] = dist[pos] + G[pos][i];
                p[i] = pos;
                g[i] = (pos == r ? i : g[pos]);
            }
        }
    }
    int mn = 5 * inf;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i] == j or p[j] == i) continue;
            if (g[i] == g[j]) continue;
            mn = min(mn, dist[i] + dist[j] + G[i][j]);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i] == j or p[j] == i) continue;
            if (g[i] == g[j]) continue;
            if (mn != dist[i] + dist[j] + G[i][j]) continue;
            vector<int> res;
            int a = i, b = j;
            while (a != r) {
                res.push_back(a);
                a = p[a];
            }
            res.push_back(a);
            reverse(res.begin(), res.end());
            while (b != r) {
                res.push_back(b);
                b = p[b];
            }
            return {mn, res};
        }
    }
    assert(false);
}

int main() {
    int n, m;
    cin >> n >> m;
    vector G(n, vector<int>(n, inf));
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        --a, --b;
        G[a][b] = G[b][a] = c;
    }
    int ans = inf;
    for (int a = 0; a < n; a++) {
        auto [len, cycle] = shortest_cycle(G, a);
        assert(int(cycle.size()) >= 3 and cycle[0] == a);
        vector<int> adj = {cycle[1], cycle.back()};
        for (int i = 0; i < n; i++) {
            if (i == a or i == adj[0] or i == adj[1]) continue;
            ans = min(ans, len + G[a][i]);
        }
        for (int i = 0; i < 2; i++) {
            int ori = G[a][adj[i]];
            G[a][adj[i]] = G[adj[i]][a] = inf;
            ans = min(ans, shortest_cycle(G, a).first + ori);
            G[a][adj[i]] = G[adj[i]][a] = ori;
        }
    }
    cout << (ans == inf ? -1 : ans) << endl;
}