AT_abc328_e（取模 MST）

题意白话

给你一张带权无向连通图：有 \(N\) 个点、\(M\) 条边，每条边 \(i\) 连接 \(u_i, v_i\)，权值是 \(w_i\)。另外给定一个正整数 \(K\)。

"生成树"就是选出 \(N-1\) 条边把所有点连起来且没有环。 对任意一棵生成树 \(T\)，把这棵树里所有边的权值加起来得到总和 \(S\)，再算 \(S \bmod K\)，这个值叫这棵树的"代价"。

问题：在所有生成树里，找出"代价"（也就是总和对 \(K\) 取模）的最小值。

输入格式

N M K
u1 v1 w1
u2 v2 w2
...
uM vM wM

• 点的编号是 \(1..N\)
• 每条边只出现一次（简单图），且整张图是连通的
• 权值满足 \(0 \le w_i < K\)

输出格式

输出一个整数：所有生成树的代价 \((\text{边权和} \bmod K)\) 的最小值。

样例 1

输入

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=361\)，对 \(328\) 取模得到 \(33\)。这正是所有生成树里最小的取模结果。

样例 2

输入

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

输出

325437688

解释：图中恰好只有一棵生成树，直接对其边权和取模即可。

样例 3

输入

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

提示：数值可能很大，注意用 64 位或更高精度整型。

约束

• \(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 < v_i \le N\)
• \(0 \le w_i < K\)
• 图是简单且连通

理解要点 & 做题提示

• 目标不是最小和，而是最小 "和对 \(K\) 的余数"。