Let \(a\) be the vertex on the cycle that is one of the endpoints of the unique edge painted black not contained in the cycle (we call this edge the tail), \(b\) and \(c\) be the vertices next to \(a\) on the cycle, and \(d\) be the other endpoint of the tail, which is not \(a\). The original conditions require \(d\) to be not contained in the cycle, but in fact it is sufficient to impose only \(d \neq b\) and \(d \neq c\) (because, if \(d\) coincides with a vertex on the cycle that is not \(a\), \(b\), or \(c\), then painting white some of the black edges yields a Q).

We exhaustively try all \(a\) (hereinafter, we assume that \(a\) is fixed). First, find a cycle containing vertex \(a\) with the minimum total cost of the edges in an \(O(N^2)\) time. As described in yukicoder No.1320 (Japanese), it can be found by the following steps:

• Construct a shortest-path tree \(T\) rooted at vertex \(a\).
• For each vertex \(j\), define the label \(L_j\) as follows:
  • \(L_j=a\) if \(j=a\);
  • \(L_j=x\) if \(j \neq a\), where \(x\) is the unique vertex that is an ancestor of vertex \(j\) (including \(j\) itself) and is a child of vertex \(a\) on \(T\).
• For each \(i\) with \(L_{A_i} \neq L_{B_i}\), let \(\text{cycle}_i\) be the cycle composed of “\(a-A_i\) path on \(T\)”, “\(a-B_i\) path on \(T\)” and “edge \(i\)”. The sought cycle is the \(\text{cycle}_i\) with the minimum total cost of the edges.

This procedure is valid because at least one edge \(i\) such that \(L_{A_i} \neq L_{B_i}\) is always contained in a cycle, and because \(T\) is a shortest-path tree.

If the cycle that we have found is contained in a Q, it is obviously optimal to choose as the tail “the edge connected to vertex \(a\) whose other endpoint is neither \(b\) nor \(c\)” with the minimum cost. All that left is to consider the case where “the edge connecting vertices \(a\) and \(b\)” or “the edge connecting vertices \(a\) and \(c\)” is the tail, which can be handled by removing each edge from the graph and start over the algorithm to find the minimum cycle as described above.

Therefore, the problem has been solved in a total of \(O(N^3)\) time.

Sample code (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;
}