AT_abc328_e [ABC328E] Modulo MST

[problemUrl]: https://atcoder.jp/contests/abc328/tasks/abc328_e 頂点に $ 1 $ から $ N $ の番号が、辺に $ 1 $ から $ M $ の番号がついた $ N $ 頂点 $ 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\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) $ - 与えられるグラフは単純かつ連結 - 入力はすべて整数 ### Sample Explanation 1 与えられるグラフは次のようになります。 !\[\](https://img.atcoder.jp/abc328/67d2cc2b93ec47687a733cd379c3c07c.png) 辺 $ 1,3,5,6 $ の $ 4 $ 本を含む全域木のコストは $ (99+86+81+95)\bmod{328}=361\bmod{328}=33 $ となります。 このグラフの全域木のコストはすべて $ 33 $ 以上であるため、$ 33 $ を出力してください。 ### Sample Explanation 2 このグラフのただ一つの全域木のコスト $ 325437688 $ を出力してください。 ### Sample Explanation 3 入力や答えが $ 32\operatorname{bit} $ 整数に収まらない場合があることに注意してください。