In the following explanation, we will refer to simple paths simply as paths and only consider paths with different endpoints.

We will determine whether there is a coloring that satisfies the condition for a fixed \(X\).

First, let’s consider the edges with weights greater than or equal to \(X\). The weight of a path using these edges is clearly at least \(X\), so they cannot be counterexamples to the condition. Therefore, we can consider these edges as non-existent when checking the condition.

Next, let’s consider the edges with weights less than \(X\). If the two vertices connected by such an edge are painted the same color, it clearly does not satisfy the condition. Therefore, the two vertices connected by such an edge must be painted different colors, and the graph composed of edges with weights less than \(X\) must be bipartite.

Finally, let’s consider how to check the condition when the graph composed of edges with weights less than \(X\) is bipartite. Whether the condition is satisfied can be considered for each connected component, and there is essentially one way to color the vertices within a connected component. Now that the coloring is determined, all that remains is to find the minimum weight of a path connecting vertices of the same color. Here, a path connecting vertices of the same color has two or more edges, and in particular, the path composed of the first two of those edges connects vertices of the same color and has weights less than or equal to the original weight. Therefore, when checking the condition, we only need to consider paths with two edges, and the minimum weight of such a path can be easily found.

From the above, for a fixed \(X\), you can determine if the condition is satisfied in \(O(N+M)\) time (if you sort in advance the weights of the edges with each vertex \(v\) as an endpoint). Since there is monotonicity with respect to \(X\) as to whether the condition is satisfied, the answer can be found in \(\displaystyle O((N+M)\log {\max_{1\leq i \leq M}{w_i}})\) time by binary search, which is sufficiently fast.

Cf. Solution without binary search

Based on the above discussion, it turns out that the answer is ultimately the smaller of the following two in the original graph:

• The minimum weight of a path using two edges
• The weight of the edge at which the graph first becomes non-bipartite when starting from a graph with \(N\) vertices and \(0\) edges and adding \(M\) edges in ascending order of weight

The former can be easily found. The latter can also be determined as follows: prepare a graph with \(2N\) vertices, add edges between vertices \(2A_i, 2B_i+1\) and between vertices \(2B_i, 2A_i+1\) in ascending order of edge weight, and check if vertices \(2A_i,2A_i+1\) are connected. This can be done in \(O((M+N)\alpha(N))\) time using dsu.

Overall, sorting of the edges is the bottleneck, and the computational complexity is \(O(N\alpha(N)+M\log M)\).