Untitled

#include <bits/stdc++.h>
using namespace std;

const int MAX = 30;
const long long INF = (1LL<<60);

struct DSU {
	vector<int> p;
	int comps; // número de componentes conexas

	DSU(int n) {
    // define tamanho N e valor padrão 0 a "p"
		p.assign(n+1, 0);
    // define os pais padrão dos vertices
		iota(p.begin(), p.end(), 0); // conta de 0 até N e espalha os valores entre as devidas posições do array "p"
		comps = n;
	}

	int id(int u) {
		return (p[u] == u ? u : p[u] = id(p[u]));
	}

	void join(int u, int v) {
		p[u] = v;
		--comps;
	}
};

struct S {
  int u, v;
  long long w;
} ns[MAX];

int N, M;

long long K;

// solução ótima global
long long ans = INF;

// backtracking | escolhendo no pior caso 8 elementos num array de tamanho 28
void back(int i, int m) {
  // se tiver N - 1 marcações então temos um caso pronto
  if(__builtin_popcount(m) == N - 1) { // conta quantos 1's tem na bitmask
    // solução ótima local
    long long soma = 0;
    DSU dsu(N);
    // passamos por todas as arestas
    for(int i = 0; i < M; ++i) {
      // se a aresta "i" estiver marcada
      if((1<<i) & m) {
        const int U = dsu.id(ns[i].u), V = dsu.id(ns[i].v);
        // se a MST forma um ciclo
        if(U == V) return;
        dsu.join(U, V);
        soma = ((soma % K) + (ns[i].w % K)) % K;
      }
    }

    // minimizamos a solução ótima global
    ans = min(ans, soma);
    return;
  }
  
  // se já chegamos a ultima posição do array de arestas
  if(i == M) return;
  
  // testando solução sem considerar a aresta i
  back(i+1, m);
  // marcando a aresta i na bitmask
  m |= (1<<i);
  // testando solução considerando a aresta i
  back(i+1, m);
}

signed main() {
  cin.tie(nullptr)->sync_with_stdio(0);

  cin>>N>>M>>K;
  for(int i = 0; i < M; ++i) {
    cin>>ns[i].u>>ns[i].v>>ns[i].w;
  }
  back(0, 0);
  cout<<ans<<'\n';
}