题目描述

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

求 $\red{G}$ 的最小生成树的边权和。

输入格式

第一行两个正整数 $\red{n,m}$。

之后的 $\red{m}$ 行，每行三个正整数 $\red{u_i,v_i,w_i}$（$\red{1\le u_i,v_i\le n}$，$\red {0\le w_i\le 10^9}$），描述一条连接结点 $\red{u_i}$ 和 $\red{v_i}$，边权为 $\red{w_i}$ 的边。

输出格式

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

样例

样例输入

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

数据范围与提示

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