题目描述

在离散数学课程的学习中，大家学习了最短树相关的知识，现在来检查一下大家的学习情况。

给定一张 $n$ 个点 $m$ 条边的带权连通无向图，点的编号从 $1$ 到 $n$，可能存在重边和自环。现在，请你求出这张图总边权和最小的支撑树（最短树）的边权之和。即，找到一颗支撑树，满足选用边的边权和最小，输出这个边权和。

输入格式

第一行两个正整数 $n, m$ ，分别表示给定无向图的点数和边数。

接下来 $m$ 行，每行三个非负整数 $u, v, w$ 表示一条连接 $u$ 和 $v$ 这两个点的无向边和这条边的边权 $w$。

输出格式

输出仅一行一个非负整数，表示最短树的边权之和。

4 5
1 3 1
1 2 2
2 3 0
3 4 3
1 4 8

4

提示

【样例解释】

选择 $(1,3)$、$(2,3)$ 和 $(3,4)$ 这三条边构成一颗支撑树。

【数据范围】

对于所有数据，满足 $1\leq n \leq 2000$，$1 \leq m \leq 3000$，边权均是 $[0, {10}^9]$ 中的整数，保证输入的图合法且满足题目中的限制条件。

请注意答案上界的大小，可能需要使用 C++ 中的 long long int 类型。