頂点数 \(8\) の完全グラフの全域木は \(262144\) 通りしかありません。 よって、与えられたグラフの全域木（を含むあまり大きくない集合の要素）を効率よく列挙できればこの問題を解くことができます。

例えば、\(N-1\) 辺の部分グラフ全体は、最大でも \({} _ {28}\mathrm{C} _ 7=1184040\) 通りしかないため、これらをすべて列挙し、全域木になっているか判定してコストの最小値を求めればよいです。

実装例は以下のようになります。 時間計算量は \(O({} _ M\mathrm{C} _ {N-1}\times M\alpha(N))\) です。

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <ranges>
#include <numeric>

int main() {
    using namespace std;

    unsigned N, M;
    unsigned long K;
    cin >> N >> M >> K;
    vector<tuple<unsigned, unsigned, unsigned long>> edges(M);
    for (auto&&[u, v, cost] : edges){
        cin >> u >> v >> cost;
        --u;
        --v;
    }

    basic_string<bool> use_edges(M, false); // M 本の辺のうち
    ranges::fill(use_edges | views::take(N - 1), true); // N - 1 本を使う
    ranges::reverse(use_edges);

    // 全域木になっているか判定するために Union-Find を使う
    vector<unsigned> uf(N), sz(N, 1);
    const auto find{[&uf](auto i) {
        while (i != uf[i])i = uf[i] = uf[uf[i]];
        return i;
    }};
    const auto unite{[&uf, &sz, find](auto i, auto j) -> bool {
        i = find(i);
        j = find(j);
        if (i == j)return false;
        if (sz[i] < sz[j])swap(i, j);
        sz[i] += sz[j];
        uf[j] = i;
        return true;
    }};

    unsigned long ans{K};
    const auto chmin{[](auto &&x, const auto &y) {
        if (x > y)x = y;
        return x;
    }};

    do
        chmin(ans, [&] {
            // Union-Find の初期化
            iota(begin(uf), end(uf), 0U);
            ranges::fill(sz, 1U);

            unsigned long cost_sum{};
            for (const auto i : views::iota(0U, M))
                if (use_edges[i]) {
                    const auto&[u, v, cost]{edges[i]};
                    if (!unite(u, v)) // 閉路ができたら
                        return K; // 十分大きい値を返す
                    cost_sum += cost;
                }
            // 全域木なら
            return cost_sum % K; // コストを返す
        }());
    while (ranges::next_permutation(use_edges).found);

    cout << ans << endl;

    return 0;
}