🟦 Prim-3 📡《联络塔铺设计划》

（稀疏边表，堆优化 Prim：$O(m\log n)$）

题目背景

兔猫信奥学院要在 $n$ 座联络塔间铺设光纤。候选线路只有 $m$ 条（不是任意两塔都能连）。 加菲老师要小兔小猫用最省的费用让所有联络塔互联；若做不到就返回失败。

题目描述

给定无向图 $n$ 点 $m$ 边，第 $i$ 条边为 $(u_i,v_i,w_i)$。 求最小生成树总权；若图不连通输出 -1。

输入格式

第一行两个整数 $n,m$。 接下来 $m$ 行，每行三个整数 $u,v,w$。

输出格式

一个整数：最小总费用或 -1。

数据范围

• $1 \le n \le 2\times 10^5$
• $0 \le m \le 3\times 10^5$
• $1 \le w \le 10^9$
• 允许重边

4 4
1 2 3
2 3 4
3 4 5
1 4 100

12

解释： 选 $1-2(3)$、$2-3(4)$、$3-4(5)$，总费用 $12$。

4 2
1 2 1
3 4 1

-1

解释： 图分成两个连通块，无法连通全部点。