题目描述
众所周知，最小生成树是指使图中所有节点连通且边权和最小时的边权子集。不过最小生成树太简单了，我们现在来思考一个稍微复杂一点的问题。
现在给定一个 \( n \) 个点，\( m \) 条边的图，每条边 \( e_i \) 都有一个权值 \( w_i \)。定义删除一条边 \( e_i \) 的代价为 \( w_i \)，并且你可以对这个图执行任意次删边操作。
设这个图的最小生成树权值和为 \( sum \)，定义一个图的最小生成树是独一无二的当且仅当这个图的边集中没有除最小生成树外的其他子集能满足权值和为 \( sum \) 且使得所有点连通。
一个图刚开始可能没有独一无二的最小生成树，现在你可以删除一些边，使得剩下的边的最小生成树大小依然为 \( sum \) 并且这个图的最小生成树是独一无二的。
我们想要知道删除的边的权值和最小是多少？
输入格式
第一行输入为 \( n \) 和 \( m \)，表示这个图的点数和边数。
接下来 \( m \) 行，每行三个值 \( u_i \)、\( v_i \)、\( w_i \)，分别代表每条边的两个端点和边权。
提示
- \( 1 \leq n \leq 2 \times 10^5 \)
- \( n - 1 \leq m \leq 2 \times 10^5 \)
- \( 1 \leq u_i, v_i \leq n \)
- \( 1 \leq w_i \leq 10^9 \)