Suppose you are given an undirected weighted graph G(V,E) and 2 vertices v, u. There are N vertices and E edges.
There can be multiple paths between those 2 vertices. For each path, select the maximum weight lying on that path. Out of all these maximum elements, find the minimum.

Initially, I was trying to solve this using DP but I couldn't find a way. Then, I thought of building a MST using Prim's Algorithm as we can get that minimum of maximums if we eliminate all the bigger elements. Eventually, I simply used Dijkstra's Algorithm where I replaced the sum function with min function. Basically, I was creating a tree rooted at v and selected N-1 minimum weight edges to make a tree.

This requires a priority queue and works in O(E log(E)). Can I optimised it to run faster. Something close to constant time (O(V + E))?