I think O(N^2) ( Prim + DFS )is the fastest way to solve this problem , is it right ?

Tell me, Why Kruscal+DFS doesn't work? I have TLE#12.
Should I write Prim?

I think Kruskal + DFS is enough.
Maybe you need to optimize your code.
Nguyen Dinh Tu ( DHSP ), my fiend , has got AC with the complexity O(N^3)( 0.89s ) . He used Prim , too.

OK, then tell me, please, how to find the second answer?
I use DFS... May be I should delete the largest vertic and
run Kruscal again?

You may try adding each non-MST edge to the MST and delete the longest MST edge in the cycle.

I don't know how, but my O(n^2) solution works 0.312 sec)