시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 429 37 20 11.236%

문제

방향성이 없는 그래프 G가 있고 이 그래프에서의 최소 스패닝 트리 T가 존재한다. 문제는 최소 스패닝 트리 T보다는 크면서 가장 작은 스패닝 트리인 'The second minimum spanning tree'를 구하는 것이다.

MST와 second MST의 모습

입력

첫째 줄에 그래프의 정점 수 V(1 ≤ V ≤ 50,000)와 에지 수 E(1 ≤ E ≤ 200,000)가 들어온다. 둘째 줄부터 E+1번째 줄까지 한 에지로 연결된 두 정점과 그 에지의 가중치가 주어진다. 음수 가중치는 없으며, 답은 int 범위를 넘지 않는다.

출력

두 번째로 작은 스패닝 트리의 값을 출력한다. 만약 스패닝 트리나 두 번재로 작은 스패닝 트리가 존재하지 않는다면 -1을 출력한다.

예제 입력

7 12
1 2 8
1 3 5
2 3 10
2 4 2
2 5 18
3 4 3
3 6 16
4 5 12
4 6 30
4 7 14
5 7 4
6 7 26

예제 출력

44

힌트

출처

  • 데이터를 추가한 사람: appa
  • 문제를 번역한 사람: author6