Informatica Online Judge

  sjimed vs 킹희승 [2398 / 095E]

Time Limit(Test case) : 1000 (ms)
Number of users who solved : 7   Total Tried : 10


The Champion of this Problem (C++) : gs18094 - ms / 1979byte
My Best Submission (C++) : N/A

[36th 신명진]
Writer ID : [gs18065]

Background

사실 sjimed와 킹희승은 태초에 같은 존재였다. 하지만 분열된 sjimed와 킹희승은 서로 자신이 진짜라는 것을 밝히기 위해 세기의 대결을 펼치기로 하였다.

신의 영역에 범접한 sjimed는 킹희승에게 이러한 놀이를 제안하였다.

주어진 그래프에서 간선을 임의로 택해, 모든 정점이 연결되도록 하면서 간선의 개수를 최소로 하고 간선의 가중치의 합을 비용이라 할 때, 비용을 최소로 하는 것이다.

하지만 이 대결의 결과는 아주 근소한 차이로 sjimed에게 돌아가게 되었다. 킹희승이 실수로 가장 적은 비용이 아니라 두 번째로 적은 비용으로 정점들을 연결한 것이다! 과연 킹희승이 사용한 비용은 얼마일까?

Input

대결에 사용하였던 그래프의 정점의 개수 n, 간선의 개수 m이 주어진다. (2<=n<=50000, 1<=m<=100000) 주어진 그래프는 연결그래프이며 자신과 자신을 연결한 간선이 없다는 것이 보장된다.

이후 m줄에 걸쳐 ui, vi, wi가 주어진다. 이는 ui와 vi가 wi의 비용으로 연결되었다는 것을 뜻한다. (0<=ui, vi<=n-1, wi는 int 범위의 음이 아닌 정수이다)

Output

킹희승이 사용한 비용을 출력하여라.(두 번째로 작은 비용이 존재하지 않으면 –1을 출력하여라.)

IO Example

입력1
4 5
0 1 1
1 2 2
2 3 2
0 2 4
3 0 3

출력1
6

입력2
4 5
0 1 2
1 2 2
2 3 2
0 2 2
3 0 2

출력2
-1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]