103284: [Atcoder]ABC328 E - Modulo MST

Problem Statement

You are given a weighted simple connected undirected graph with $N$ vertices and $M$ edges, where vertices are numbered $1$ to $N$, and edges are numbered $1$ to $M$. Additionally, a positive integer $K$ is given.
Edge $i\ (1\leq i\leq M)$ connects vertices $u_i$ and $v_i$ and has a weight of $w_i$.

For a spanning tree $T$ of this graph, the cost of $T$ is defined as the sum, modulo $K$, of the weights of the edges in $T$. Find the minimum cost of a spanning tree of this graph.

Constraints

• $2\leq N\leq8$
• $N-1\leq M\leq\dfrac{N(N-1)}2$
• $1\leq K\leq10^{15}$
• $1\leq u_i\lt v_i\leq N\ (1\leq i\leq M)$
• $0\leq w_i\lt K\ (1\leq i\leq M)$
• The given graph is simple and connected.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print the answer.

Sample Input 1

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

Sample Output 1

33

The given graph is shown below:

The cost of the spanning tree containing edges $1,3,5,6$ is $(99+86+81+95)\bmod{328}=361\bmod{328}=33$. The cost of every spanning tree of this graph is at least $33$, so print $33$.

Sample Input 2

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

Sample Output 2

325437688

Print the cost of the only spanning tree of this graph, which is $325437688$.

Sample Input 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

Sample Output 3

11360716373

Note that the input and the answer may not fit into a $32\operatorname{bit}$ integer.

问题描述

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

设图的生成树$T$的花费为边的权重之和对$K$取模的结果。 找出该图生成树的最小花费。

约束条件

• $2\leq N\leq8$
• $N-1\leq M\leq\dfrac{N(N-1)}2$
• $1\leq K\leq10^{15}$
• $1\leq u_i\lt v_i\leq N\ (1\leq i\leq M)$
• $0\leq w_i\lt K\ (1\leq i\leq M)$
• 给定的图是简单且连通的。
• 所有输入值都是整数。

输入

输入从标准输入给出，格式如下：

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

输出

打印答案。

样例输入1

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

样例输出1

33

给定的图如下所示：

包含边$1,3,5,6$的生成树的花费是$(99+86+81+95)\bmod{328}=361\bmod{328}=33$。 该图中每个生成树的花费至少为$33$，所以打印$33$。

样例输入2

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

样例输出2

325437688

打印该图中唯一生成树的花费，即$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

样例输出3

11360716373

请注意，输入和答案可能不适应$32$位整数。