If you fix the “tail” of the Q as \((u, v)\) where \(u\) is the vertex on the cycle and \(v\) is the vertex not on the cycle, you can find the cheapest cycle going from \(u\) to itself on the graph without \(v\) and its edges, using shortest-path tree.

At first glance this could cost up to \(O(N^4)\) time, as there are up to \(O(N^2)\) edges that might be the tail, and finding the cheapest cycle on the subgraph costs \(O(N^2)\).

However, note that for any given cycle from arbitrary vertex \(u\) to itself, you can try to make a Q out of the cheapest edge that isn’t one of \(u\)’s neighbors in the cycle (and if you fail cause the tail happens to be a part of the cycle, you can make a cheaper proper Q by removing some edges).

Thus, the tail of the cheapest Q is limited to be one of the \(3\) cheapest edges from some vertex \(u\). Thus you only have \(O(N)\) tail candidates to check, making the solution take \(O(N^3)\) time.