N個の交差点、R本の道がある。(1<=N<=5000, 1<=R<=10万)
1からNまでの距離で、最短距離より長い、2番目の最短距離はどのくらいになるか。
その距離を達成するためには、同じ交差点、同じ道を何度も使用して構わず、2番目の最短距離は必ず存在する。

最短距離ならDijkstra。
普通のDijkstraでは各点までの最短距離を計算するが、この問題では、各点までの最短距離と、2番目の最短距離を覚えるように拡張してしまえばよい。

3255.cpp