U. 最小生成树

problem_type.default

1000ms

256MiB

대회가 끝났으므로 답안을 제출할 수 있습니다. "믄제에서 열기"를 누르세요.

题目描述

给定结点数为 $n$ ，边数为 $m$ 的带权无向连通图 $G$ ，所有结点编号为 $1,2,...,n$ 。

求 $G$ 的最小生成树的边权和。

第一行两个正整数 $n,m$ 。

之后的 $m$ 行，每行三个正整数 $u_i,v_i,w_i$ ，描述一条连接结点 $u_i$ 和 $v_i$ ，边权为 $w_i$ 的边。

一个整数表示 $G$ 的最小生成树的边权和。

$1\le n\le 2\times 10^5$ ， $0\le m\le 5\times 10^5$ 。

$1\le u_i,v_i\le n$ ， $0\le w_i\le 10^9$