题目描述

Kickstartia 的乡村由 $V$ 个村庄组成，村庄之间由 $E$ 条双向道路连接。由于居民们喜欢道路建设的多样性，没有两条道路的长度相同。每条道路恰好连接两个不同的村庄，并且没有两条道路连接同一对村庄。

新国王渴望展示他的进步性，他想制定一个计划：每个村庄专门生产一种食物——要么水果，要么蔬菜。如果一个村庄生产水果，那么它需要找到一条到某个生产蔬菜的村庄的最短路径（可能经过多条道路）。类似地，如果一个村庄生产蔬菜，它需要找到一条到某个生产水果的村庄的最短路径。

为了保持一切顺利运转，国王希望最小化每个村庄为获取自己不生产的食物所需旅行距离的平均值。

可能存在多个计划使这个平均距离最小，因此国王希望你能告诉他这样的计划有多少个。两个计划被视为不同，如果存在某个村庄在一个计划中生产水果而在另一个计划中生产蔬菜。国王保证存在一个计划使得每个村庄都能同时获得水果和蔬菜。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $V$ 和 $E$，分别表示村庄的数量和道路的数量。村庄编号为 $1$ 到 $V$。接下来 $E$ 行，第 $i$ 行包含三个整数 $A_i$、$B_i$ 和 $L_i$，表示第 $i$ 条道路连接村庄 $A_i$ 和 $B_i$，长度为 $L_i$。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述国王所求的答案。

2
3 3
1 2 1
1 3 6
2 3 4
6 5
1 2 6
3 4 0
5 6 7
3 5 1
4 6 2

Case #1: 2
Case #2: 16

提示

在样例 #1 中，一种可能的计划是让村庄 $1$ 和 $3$ 生产水果，村庄 $2$ 生产蔬菜。村庄 $1$ 和 $2$ 可以相互前往获取各自缺乏的食物，因此它们都需要旅行距离 $1$。村庄 $3$ 需要前往村庄 $2$ 获取蔬菜，旅行距离为 $4$。总平均距离为 $(1 + 1 + 4)/3 = 2$，这是可能的最小值。还有另一个最优计划（村庄 $1$ 和 $3$ 生产蔬菜，村庄 $2$ 生产水果），因此最终答案为 $2$。

在样例 #2 中，共有 $16$ 种可能的计划。一种方式是让村庄 $1$、$3$ 和 $5$ 生产水果，村庄 $2$、$4$ 和 $6$ 生产蔬菜。村庄 $1$ 和 $2$ 需要相互前往获取缺乏的食物。村庄 $3$ 和 $5$ 可以前往村庄 $4$ 获取蔬菜，村庄 $4$ 和 $6$ 可以前往村庄 $3$ 获取水果。平均距离为 $(6 + 6 + 0 + 1 + 0 + 2)/6 = 2.5$，这是可能的最小值。即使两个村庄由长度为 $0$ 的道路连接，它们仍然被视为不同的村庄。

限制条件

$1 \le T \le 100$。

$1 \le E \le \min(1000, V \times (V - 1) / 2)$。

对于所有 $i$，$0 \le L_i \le 10^5$。

对于所有 $i \neq j$，$L_i \neq L_j$。

对于所有 $i$，$1 \le A_i < B_i \le V$。

对于所有 $i \neq j$，$(A_i, B_i) \neq (A_j, B_j)$。

至少存在一个计划使得每个村庄都能获得两种食物。

小数据集（测试集 1 – 可见）

$2 \le V \le 10$。

大数据集（测试集 2 – 隐藏）

$2 \le V \le 50$。

翻译由 DeepSeek V4 Pro 完成