심판의 실수

프로그래밍 대회의 문제를 출제하는 데는 오랜 시간이 걸린다. 몇 달 전, 심판들은 문제를 공모했고 Kevin은 Figure J.1의 문제로 응답했다.

Figure J.1: Kevin이 제안한 원래 문제.

이 문제는 Divisionals 대회에서 사용될 예정이었지만, 우리(심판들)가 실수를 저질렀다. 풀이를 작성하던 중, 우리 중 한 명이 공식 입력의 정수들을 실수로 정렬해 버렸다. 우리는 C와 R의 값은 알아낼 수 있었지만, 나머지 3R개의 정수의 순서는 알아낼 수 없었다.

원래 데이터를 복원하는 대신, 우리는 조금 다른 질문을 하려고 한다. 이 3R개의 정수는 여러 가지 도로망에 대응될 수 있다. 데이터가 나타낼 수 있는 모든 도로망 중에서, 원래 문제의 출력으로 가능한 가장 작은 값은 무엇인가? (즉, 나타낼 수 있는 모든 도로망 중에서 가장 저렴한 유지보수 계획의 비용은 얼마인가?)

입력의 첫 줄에는 두 정수 C (2 ≤ C ≤ 100 000)와 R (1 ≤ R ≤ 100 000)이 주어진다. C는 도시의 수, R은 도로의 수이다.

둘째 줄에는 3R개의 정수가 주어지며, 이는 Figure J.1의 원래 문제에서의 u, v, w 값이다. 각 값은 1 이상 100 000 이하이다. 이 정수들은 비내림차순으로 정렬되어 있다.

입력은 원래 문제의 제약 조건을 만족하는 적어도 하나의 도로망에 대응됨이 보장된다.

나타낼 수 있는 모든 도로망 중에서 가장 저렴한 유지보수 계획의 비용을 출력한다.