U615388 最小生成树

给定一个无向图 $ G = (V, E) $，其中包含 $ n $ 个顶点（编号从 $ 1 $ 到 $ n $）和 $ m $ 条带权边。每条边 $ e_i \in E $（$ 1 \leq i \leq m $）由三元组 $ (u_i, v_i, w_i) $ 表示，其中 $ u_i $ 和 $ v_i $ 是该边连接的两个顶点，$ w_i $ 是该边的非负整数权重（即 $ w_i \geq 0 $）。图中不存在重边和自环。 现在，对于每一条边 $ e_i $（按输入顺序编号为 $ i = 1, 2, \dots, m $），你需要考虑从图 $ G $ 中**临时移除**该边后所形成的新图 $ G_i = (V, E \setminus \{e_i\}) $，并计算该新图的**最小生成树**（Minimum Spanning Tree, 简称 MST）的**总权重**。 具体而言，对于每个 $ i \in \{1, 2, \dots, m\} $，执行以下操作： - 构造图 $ G_i = (V, E \setminus \{e_i\}) $； - 若 $ G_i $ **不连通**（即无法通过剩余边将所有 $ n $ 个顶点连接成一个连通分量），则输出 $ -1 $； - 否则，计算 $ G_i $ 的最小生成树的边权总和，并输出该值。 你的任务是依次对每条边 $ e_1, e_2, \dots, e_m $ 执行上述过程，并输出共 $ m $ 行结果，第 $ i $ 行对应移除第 $ i $ 条边后的答案。

输入的第一行包含两个整数 $ n $ 和 $ m $，分别表示图中的顶点数和边数，满足 $ 1 \leq n \leq 10^5 $，$ 1 \leq m \leq 10^6 $。 接下来的 $ m $ 行，每行包含三个整数 $ u_i, v_i, w_i $，表示第 $ i $ 条边连接顶点 $ u_i $ 与 $ v_i $，其权重为 $ w_i $。保证 $ 1 \leq u_i, v_i \leq n $，$ u_i \ne v_i $，且 $ 0 \leq w_i \leq 10^9 $。

输出共 $ m $ 行，每行一个整数。 第 $ i $ 行（$ 1 \leq i \leq m $）表示在从原始图中移除第 $ i $ 条输入边后，剩余图的最小生成树的总权重；如果此时图不连通，则输出 $ -1 $。

#### 数据范围与约束 - $ 1 \leq n \leq 10^5 $ - $ 1 \leq m \leq 10^6 $ - $ 1 \leq u_i, v_i \leq n $，且 $ u_i \ne v_i $ - $ 0 \leq w_i \leq 10^9 $