给定结点数为 nnn ,边数为 mmm 的带权无向连通图 GGG,所有结点编号为 1,2,3,...,n1,2,3,...,n1,2,3,...,n。
求 GGG 的最小生成树的边权和。
输入
第一行两个正整数 n,m (1≤n≤2×105,1≤m≤5×105)n,m \ (1 \leq n \leq 2 \times 10^5,1 \leq m \leq 5 \times 10^5)n,m (1≤n≤2×105,1≤m≤5×105)。
之后的 mmm 行,每行三个正整数 u,v,w (1≤u,v≤n,0≤w≤109)u,v,w \ (1 \leq u,v \leq n,0 \leq w \leq 10^9)u,v,w (1≤u,v≤n,0≤w≤109),表示 uuu 和 uuu 有边权为 www 的边。
输出
一个整数,答案。
样例
7 12 1 2 9 1 5 2 1 6 3 2 3 5 2 6 7 3 4 6 3 7 3 4 5 6 4 7 2 5 6 3 5 7 6 6 7 1
16