도시 분할 계획

마을에는 N개의 집과 M개의 양방향 길이 있다. 각 길에는 그 길을 유지하는 데 드는 비용이 있으며, 입력으로 주어지는 마을에서는 어떤 두 집 사이에도 항상 이동 경로가 존재한다.

마을을 정확히 두 개의 분리된 마을로 나누려고 한다. 두 마을은 각각 집을 하나 이상 가져야 하며, 같은 마을 안의 임의의 두 집 사이에는 길들을 따라 이동할 수 있어야 한다.

나눈 뒤에는 서로 다른 두 마을을 잇는 길을 모두 없앨 수 있다. 또한 각 마을 내부에서도 연결 상태가 유지되는 한 불필요한 길을 더 없앨 수 있다. 이 조건을 만족하도록 길을 남겼을 때, 남은 길들의 유지비 합의 최솟값을 구하시오.

첫째 줄에 집의 개수 N과 길의 개수 M이 주어진다. N은 2 이상 100,000 이하인 정수이고, M은 1 이상 1,000,000 이하인 정수이다.

다음 M개의 줄에는 길의 정보가 A B C 형태로 주어진다. 이는 A번 집과 B번 집을 연결하는 양방향 길의 유지비가 C라는 뜻이다. C는 1 이상 1,000 이하인 정수이다.

입력으로 주어지는 그래프는 항상 연결되어 있다.

조건을 만족하도록 길을 없앤 뒤, 남은 길들의 유지비 합이 가질 수 있는 최솟값을 출력한다.