두 번째로 작은 스패닝 트리

무방향 그래프 G가 주어진다. G의 최소 스패닝 트리보다 총가중치가 크면서, 그중 총가중치가 가장 작은 스패닝 트리의 값을 구하라. 이러한 트리를 두 번째로 작은 스패닝 트리라고 한다.

그림은 최소 스패닝 트리와 두 번째로 작은 스패닝 트리의 예시이다.

첫째 줄에 그래프의 정점 수 V(1 <= V <= 50,000)와 간선 수 E(1 <= E <= 200,000)가 주어진다. 다음 E개 줄에는 간선이 연결하는 두 정점과 그 간선의 가중치가 주어진다. 가중치는 0 이상 100,000 이하의 정수이다. 답은 (2^{31}-1)을 넘지 않는다.

정점 번호는 1 이상 V 이하이다.

두 번째로 작은 스패닝 트리의 총가중치를 출력한다. 스패닝 트리가 존재하지 않거나, 최소 스패닝 트리보다 총가중치가 큰 스패닝 트리가 존재하지 않으면 -1을 출력한다.