문제
훈이는 큰 건물의 네트워크 관리인이다. 오랫동안 네트워크를 새로 설치하고 또 필요없는 곳은 제거하면서 관리해 오다보니 전체적인 시스템이 너무 복잡하게 되고 말았다. 그래서 훈이는 네트워크의 전체적인 연결상태를 파악한 후 불필요한 선들을 모두 제거하기로 하였다. 선들은 컴퓨터끼리 모두 연결만 되어 있으면 된다. 즉 1번과 2번이 연결되고 2번과 3번이 연결되어 있으면 1번과 3번도 연결된 것이다.
훈이는 모든 컴퓨터를 연결시킬 수 있는 가장 짧은 선들만을 남기고 모두 제거하려고 했으나 그렇게 되면 해커들이 네트워크 연결상태를 모두 알게 되어 공격을 받을 수 있을 것 같아 다른 방법을 생각하게 되었다. 고민끝에 훈이가 생각한 것은 모든 컴퓨터를 연결시킬 수 있는 두번째로 짧은 경로를 선택하여 그 선들만을 남기고 나머지는 모두 제거하는 것이다.
훈이가 파악한 이 건물의 네트워크 연결 정보가 주어질 때 훈이의 생각대로 불필요한 선들을 제거할 경우 제거되는 선들의 전체 길이는 얼마인지 알 수 있는 프로그램을 작성해 보자.
입력
입력의 첫줄에는 컴퓨터의 개수 N(1≤N≤1,000)과 현재 연결되어 있는 선들의 개수 M(1≤M≤10,000) 이 주어진다. 컴퓨터의 번호는 1번부터 N번까지로 구분된다.
그 다음줄부터 M개의 줄에 걸쳐 각 줄마다 세개의 정수 X, Y, L이 주어지는데 X와 Y는 컴퓨터의 번호이고 L은 X와 Y를 연결한 선의 길이이다. (1 ≤ L ≤10,000,000)
두 컴퓨터 사이에 두개의 이상의 선이 연결된 경우는 없으며 선들의 길이의 합은 20억을 넘지 않는다.
출력
첫 줄에 제거해야 할 선들의 총 길이를 출력한다. 만약 그런 방법이 존재하지 않으면 -1을 출력한다.
예제
4 5
1 2 13
1 3 12
2 3 7
2 4 47
3 4 10
59
힌트
로그인해야 코드를 작성할 수 있어요.