最短树问题

题目大意

给你一张带权、连通、无向图，有 (n) 个点、(m) 条边（允许重边和自环）。 请从这些边里挑出 (n-1) 条，把所有点都连起来（形成一棵"支撑树"/生成树），并且让选中边的权值总和最小。把这个最小总权值输出即可。 这棵"最省边权的生成树"就叫最小生成树（MST）。

你需要做什么

从输入的图中，找出最小生成树，输出它的边权和。

自环（(u=v) 的边）对生成树没用； 重边（同一对点有多条边）可以选其中更便宜的那条，只要能让总和更小。

输入格式

• 第一行：两个整数 (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+0+3=4)，且能连通所有点，这是最小的。

数据范围

• \(1 \le n \le 2000\)
• \(1 \le m \le 3000\)
• 边权 (w) 是区间 \([0, 10^9]\) 内的整数
• 图保证连通、输入合法
• 答案可能很大，注意用 64 位整型（C++ 建议 long long）

小贴士（思路提示，非必须）

• 用Kruskal 或 Prim 都能做：

  • Kruskal：把所有边按权值从小到大排序，依次尝试加入，配合并查集避免成环。时间大约 (O(m \log m))。
  • Prim：从任意点出发，每次把"代价最小的外连边"加入，用堆优化为 (O(m \log n))。
• 忽略自环；重边按权值自然会在排序/挑选时被处理到更优解。