깊은 바닷속에 설치된 관측 시스템에는 N개의 중계기와, 중계기들을 서로 연결하는 M개의 통신 채널이 있다. 각 통신 채널은 양방향으로 신호를 보낼 수 있으며, 채널마다 정기 점검에 필요한 비용이 정해져 있다. 현재는 어떤 중계기에서 출발하더라도 여러 통신 채널을 거쳐 다른 모든 중계기로 신호를 보낼 수 있다.

해양 연구소는 관측 임무를 두 개의 독립 구역으로 나누어 운영하려고 한다. 각 중계기는 두 구역 중 정확히 하나에 속해야 하며, 두 구역 모두 적어도 하나의 중계기를 포함해야 한다. 또한 같은 구역에 속한 임의의 두 중계기 사이에는, 그 구역 안에 남겨진 통신 채널만을 사용해서 신호를 보낼 수 있어야 한다.

구역을 나누고 나면 서로 다른 구역을 잇는 통신 채널은 더 이상 필요하지 않다. 같은 구역 안에서도 연결성만 유지된다면 일부 통신 채널을 추가로 비활성화할 수 있다. 연구소는 조건을 만족하도록 통신 채널을 남기되, 남겨진 채널들의 정기 점검 비용 합이 최소가 되기를 원한다.

가능한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 중계기의 개수 N, 통신 채널의 개수 M이 주어진다. N은 2 이상 100,000 이하인 정수이고, M은 1 이상 1,000,000 이하인 정수이다.

그 다음 줄부터 M줄에 걸쳐 통신 채널의 정보 A B C가 주어진다. 이는 A번 중계기와 B번 중계기를 잇는 양방향 통신 채널의 정기 점검 비용이 C라는 뜻이다. C는 1 이상 1,000 이하인 정수이다.

임의의 두 중계기 사이에 신호를 보낼 수 있는 입력만 주어진다.

출력

첫째 줄에 조건을 만족하도록 남긴 통신 채널들의 정기 점검 비용 합의 최솟값을 출력한다.

예제 입력 1

7 12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

예제 출력 1

8