$N$개의 정점과, 가중치 있는 간선 $M$개로 이루어진 무향 그래프 $G$가 주어진다. $G$의 최소 스패닝 트리를 구해보자.

$N$개의 정점을 최소한의 비용으로 모두 연결하는 트리를 구하면 된다. $G$는 다음을 만족한다.

• 어떤 정점 쌍을 골라도 둘을 잇는 경로는 반드시 존재한다.
• 자기 자신에게 향하는 간선은 존재하지 않는다.
• 어떤 두 정점을 직접적으로 잇는 간선은 두 개 이상 존재하지 않는다.
  

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다. $(1 ≤ N ≤ 50,000; 1 ≤ M ≤ 200,000)$

둘째 줄부터 $M$개의 줄에 걸쳐 $u, v, w$가 공백으로 구분되어 주어진다. $(1 ≤ u, v ≤ N; 1 ≤ w ≤ 10,000)$