取模最小生成树

题目描述

给定一个带权简单连通无向图，有 $N$ 个顶点和 $M$ 条边，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。此外，给定一个正整数 $K$。

边 $i\ (1 \le i \le M)$ 连接顶点 $u_i$ 和 $v_i$，权重为 $w_i$。

对于该图的一棵生成树 $T$，定义 $T$ 的花费为 $T$ 中各边权重之和对 $K$ 取模后的值。 求该图的生成树的最小花费。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$ $K$
$u_1$ $v_1$ $w_1$
$u_2$ $v_2$ $w_2$
$\vdots$
$u_M$ $v_M$ $w_M$

输出格式

输出答案。

样例

5 6 328
1 2 99
1 3 102
2 3 86
2 4 94
2 5 95
3 4 81

33

包含边 $1, 3, 5, 6$ 的生成树的花费为 $(99+86+81+95)\bmod{328}=361\bmod{328}=33$。 该图所有生成树的花费至少为 $33$，因此输出 $33$。

6 5 998244353
1 2 337361568
1 6 450343304
2 3 61477244
2 5 745383438
4 5 727360840

325437688

输出该图唯一生成树的花费，即 $325437688$。

8 28 936294041850197
1 2 473294720906780
1 3 743030800139244
1 4 709363019414774
1 5 383643612490312
1 6 557102781022861
1 7 623179288538138
1 8 739618599410809
2 3 857687812294404
2 4 893923168139714
2 5 581822471860662
2 6 740549363586558
2 7 307226438833222
2 8 447399029952998
3 4 636318083622768
3 5 44548707643622
3 6 307262781240755
3 7 12070267388230
3 8 700247263184082
4 5 560567890325333
4 6 704726113717147
4 7 588263818615687
4 8 549007536393172
5 6 779230871080408
5 7 825982583786498
5 8 713928998174272
6 7 751331074538826
6 8 449873635430228
7 8 11298381761479

11360716373

注意输入和答案可能超出 $32\operatorname{bit}$ 整数能表示的范围。

数据范围

• $2 \le N \le 8$
• $N-1 \le M \le \dfrac{N(N-1)}2$
• $1 \le K \le 10^{15}$
• $1 \le u_i \lt v_i \le N\ (1 \le i \le M)$
• $0 \le w_i \lt K\ (1 \le i \le M)$
• 给定的图是简单且连通的。
• 输入均为整数。