The sought value is the minimum cost, multiplied by \(-1\), to travel from vertex \(X\) to vertex \(Y\) on a graph with a directed graph with edges from vertex \(A_i\) to vertex \(B_i\) with cost \(-C_i\) and edges from \(B_i\) to \(A_i\) with cost \(C_i\).

If \(X\) and \(Y\) does not belong to the same connected component, the answer is nan. Since we can consider each connected component independently, we assume that the graph is connected.

For a fixed vertex \(V\), we find the cost from \(V\) to each vertex.
Here, the cost from \(V\) to some vertex is not unique if and only if there is a closed walk with a non-zero cost.

If there is a closed walk with a non-zero cost, we can reduce the cost as much as you want by going around this loop, so the answer between any two points is inf.

Otherwise, the cost of any closed walk is \(0\). Denoting by \(d(x,y)\) the minimum cost from vertex \(x\) to vertex \(y\), for all \(x\) and \(y\)
it holds that \(d(x,y)+d(y,x)=0\) and \(d(x,y)+d(y,V)+d(V,x)=0\), so \(d(x,y)=d(V,y)-d(V,x)\). Since the cost from \(V\) to each vertex is unique, we can find each \(d(V,x)\) with a BFS (Breadth-First Search) or a DFS (Depth-First Search).

Hence, after an \((N+M)\) precalculation, each query can be answered in an \(O(1)\) time each.

Writer’s solution (C++)
Note that this solution exploits DSU (Disjoint Set Union), costing \(O(N+M\alpha(N))\) for precalculation and \(O(\alpha(N))\) for each query.