修建公路2 ### 题目描述 $L$ 城一共有 $N$ 个小区。 小明是城市建设的规划者，他计划在城市修 $M$ 条路，每修建一条路都要支付工人们相应的工钱（需要支付的工钱 $=$ 路的长度）。 小明所拿到的经费并不够支付修建 $M$ 条路的工钱，于是迫于无奈，他只能将计划改变为修建若干条路，使得 $N$ 个小区之间两两联通。 为了防止一些未知因素的发生，小明希望你能帮他设计一个 $B$ 计划，内容同样是修建道路使得 $N$ 个小区之间两两联通。不过要求 $B$ 计划和小明的计划不能完全相同（即两计划至少有一条修建的道路不相同）。 请编写程序计算完成 $B$ 计划最少的开销为多少。 ### 输入描述 输入第一行包含三个正整数 $N,M$。 第 $2$ 到 $M + 1$ 行每行包含三个正整数 $u,v,w$，表示 $u\leftrightarrow v$ 之间存在一条距离为 $w$ 的路。 $1\leq N \leq 10^5$，$0 \leq m \leq 3\times10^5$，$1 \leq u_i, v_i\leq N$，$0 \leq w_i \leq 10 ^ 9$。 ### 输出描述 输出占一行，包含一个整数，表示完成 $B$ 计划所需的最低开销。 数据保证必定存在 $B$ 计划。 ### 输入输出样例 #### 示例 1 >输入 ```txt 3 3 1 2 1 2 3 1 1 3 2 ``` >输出 ```txt 3 ```