1005. 大户爱的生成树2

题目描述

大户爱有两张图，图 A 为一张 N 个点、M 条边的无向带权图，图 B为一张 N 个点的完全图，图 B 中任意两点间的边权为图 A 中对应两点的最小割。给定图 A，求图 B 的最小生成树的边权之和。最小割定义：给定一个无向带权图 G，点集为 V，边集为 E，其中每条边 u ↔ v有权值 wu,v。

一个割是指将点集 V 划分为两个非空不相交集合 S 和 T，即：

• S∪T =V

• S∩T =∅

• S=∅

• T =∅

该割的容量定义为所有跨越 S 和 T 的边的权值之和：

c=

∑ wu,v

u∈S,v∈T

最小割是指所有可能割中容量最小的割，其容量记为：

λ = min c∅=S⊂V

对于图 G 中任意两个指定顶点 s 和 t，s 和 t 之间的最小割定义为：在所有满足 s ∈ S、t ∈ T 的割中，容量的最小值，即：

λst =

min

∅=S⊂V, s∈S, t∈T

c

输入格式

第一行输入一个整数 T，表示数据组数。每组数据首先输入两个整数 N 和 M，表示图 A 的点数和边数。接下来输入 M 行，每行三个整数 x, y, z，表示 x 和 y 之间有一条权值为 z 的边。不保证图连通，且可能出现重边和自环。

1 ≤ T ≤ 6，1 ≤ N ≤ 600，∑ N ≤ 2000，0 ≤ M ≤ N (N2−1)，0 ≤z ≤ 109。

输出格式

对于每组数据，输出一行一个整数，表示图 B 的最小生成树的边权之和。

样例输入

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

样例输出

12

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）