최소 스패닝 트리

문제

$N$개의 정점과 $M$개의 간선으로 이루어진 연결 그래프가 주어진다. 각 정점은 $1$부터 $N$까지 번호가 매겨져 있고, 각 간선에는 가중치가 매겨져 있다. 이 그래프의 최소 스패닝 트리(MST, Minimum Spanning Tree)를 구해보자.

스패닝 트리는 그래프의 모든 정점을 포함하면서 사이클 없이 연결된 부분 그래프를 의미한다. 최소 스패닝 트리는 가능한 모든 스패닝 트리 중 가중치의 합이 최소인 스패닝 트리를 의미한다.

왼쪽 그림의 최소 스패닝 트리는 오른쪽 그림과 같다.

입력

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. ($2\le N\le 100\,000; N-1\le M\le 300\,000$)

둘째 줄부터 $M$개의 줄에 걸쳐 세 정수 $u$, $v$, $w$가 공백으로 구분되어 주어진다. $u$번 정점과 $v$번 정점을 잇는 가중치가 $w$인 무향 간선이 존재함을 의미한다. ($1\le u, v\le N; u\neq v; -10^9\le w\le 10^9$)

두 정점을 잇는 간선이 여러 개 주어질 수도 있음에 유의하며, 입력으로 주어지는 그래프는 연결 그래프임이 보장된다.

출력

최소 스패닝 트리의 가중치의 합을 출력한다.

예제 입력 1

6 7
4 1 5
1 6 3
6 5 1
1 5 -5
2 5 0
1 2 -3
3 2 2

예제 출력 1

0

예제 입력 2

3 4
1 2 10
3 2 1
1 2 1000
3 2 100

예제 출력 2

11