AT_abc328_e [ABC328E] Modulo MST

给定一个有 $N$ 个顶点、$M$ 条边的带权无向连通简单图，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$，以及一个正整数 $K$。 第 $i$ 条边 $(1\leq i\leq 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$

请输出答案。

## 限制条件 - $2\leq N\leq 8$ - $N-1\leq M\leq\dfrac{N(N-1)}{2}$ - $1\leq K\leq 10^{15}$ - $1\leq u_i < v_i \leq N\ (1\leq i\leq M)$ - $0\leq w_i < K\ (1\leq i\leq M)$ - 给定的图是简单且连通的 - 所有输入均为整数 ## 样例解释 1 给定的图如下所示。  包含边 $1,3,5,6$ 的 $4$ 条边的生成树的代价为 $(99+86+81+95)\bmod{328}=361\bmod{328}=33$。 该图所有生成树的代价都不小于 $33$，因此输出 $33$。 ## 样例解释 2 该图只有一棵生成树，其代价为 $325437688$，请输出该值。 ## 样例解释 3 请注意，输入和答案可能超出 $32$ 位整数的范围。 由 ChatGPT 4.1 翻译