두 번째로 작은 스패닝 트리
시간 제한2초메모리 제한128 MB
최소 스패닝 트리를 구한 뒤, 그보다 가중치가 엄밀히 더 큰 스패닝 트리 중 가장 작은 것을 찾고 없으면 -1을 출력합니다.
문제
무방향 그래프 G가 주어진다. G의 최소 스패닝 트리보다 총가중치가 크면서, 그중 총가중치가 가장 작은 스패닝 트리의 값을 구하라. 이러한 트리를 두 번째로 작은 스패닝 트리라고 한다.
그림은 최소 스패닝 트리와 두 번째로 작은 스패닝 트리의 예시이다.
입력
첫째 줄에 그래프의 정점 수 V(1 <= V <= 50,000)와 간선 수 E(1 <= E <= 200,000)가 주어진다. 다음 E개 줄에는 간선이 연결하는 두 정점과 그 간선의 가중치가 주어진다. 가중치는 0 이상 100,000 이하의 정수이다. 답은 (2^{31}-1)을 넘지 않는다.
정점 번호는 1 이상 V 이하이다.
출력
두 번째로 작은 스패닝 트리의 총가중치를 출력한다. 스패닝 트리가 존재하지 않거나, 최소 스패닝 트리보다 총가중치가 큰 스패닝 트리가 존재하지 않으면 -1을 출력한다.