Re: O(N^2) solution...

My 0.093 N square solution:

1) Compute MST with Kruskal in E logE.

2) For each pair of vertices in MST compute dp[u][v] the cost of largest edge on path from u to v. This can be done by calling N depth first searches. DFS runs in O(E) and there is N - 1 edge in a MST. So this step takes (N^2) time.

3) For each edge (u, v) that isn't in a MST try to relax answer with { MST_COST - dp[u][v] + weight(u, v) }. This step is done in O(E).

So, the running time of this solution is O(ElogE + E + N^2) = O(N^2).