P12007 【MX-X10-T3】[LSOT-4] 全国联赛？

> 你真的以为我们能打进全国联赛吗？

北宇治的吹奏部一共有 $n$ 个学生，学生的编号为 $1$ 到 $n$。在泷昇到来之前已经建立了 $m$ 对配合关系（$0 \le m \le n - 1$），每对配合关系 $u,v,w$ 表示在 $u$ 或 $v$ 演奏后另一人能在 $w$ 单位的时间后立刻演奏完成配合。若两人没有直接的配合关系，也可以通过多次的配合关系来间接完成配合，他们造成的误差时间是中间每次配合花费的时间之和。 现在的吹奏部简直乱的像一盘散沙！为此，泷昇有 $n-m-1$ 种特训方案。第 $i$ 种方案可以让任意两个成员建立配合关系，最终训练的效果能让二人在 $a_i$ 的时间内完成配合。定义不协调度为对于所有的 $1\le x

无

无

**【样例解释 #1】** 之前的配合关系形如：  最优秀的训练方式训练之后的配合关系形如：  这样的话，$(1,7)$ 的误差时间的最小值是 $4$，方案是通过 $(1,2)$、$(2,3)$、$(3,7)$ 依次进行配合。 类似的，所有误差时间之和是 $76$。 可以证明不存在更优秀的合法方案。 **【数据范围】** **本题采用捆绑测试。** - 子任务 1（13 分）：$n\le 6$。 - 子任务 2（22 分）：$n\le 2000$。 - 子任务 3（18 分）：在建立新的配合关系前，任意两个可以配合的成员都可以通过不超过一个中间的成员间接配合。 - 子任务 4（19 分）：$a_i=0,w=1$。 - 子任务 5（15 分）：$a_i$ 全部相同。 - 子任务 6（13 分）：无特殊性质。 对于全部的数据，$0\le m