最短树问题

题目描述

给定一张包含 \(n\) 个点、\(m\) 条边的带权连通无向图（允许重边与自环，点从 \(1\sim 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

样例说明：一种可行的最小生成树选边为 \({(2,3,0),(1,3,1),(3,4,3)}\)，总权为 \(0+1+3=4\)。

数据范围与提示

• \(1 \le n \le 100000\)
• \(1 \le m \le 300000\)
• \(0 \le w \le 10^9\)
• 输入保证图连通且合法。

提示：答案可能超过 \(32\) 位整数范围，建议在 C++ 中使用 \(long\) \(long\)。 解法建议：可用 \(Kruskal\)（并查集）或 \(Prim\)（最小堆）算法，时间复杂度分别约为 \(O(m \log m)\) 与 \(O(m \log n)\)。