爆搜。

#include <bits/stdc++.h>
#define int long long
#define INF 0x3fffffff
#define INFF 1e18
#define endl '\n'

using namespace std;

const int N = 10, M = 50;

int U[M], V[M], W[M], fa[N];
int n, m, k, ans = INFF;

int find(int u) {
	return u == fa[u] ? u : fa[u] = find(fa[u]);
}

void dfs(int dep, int lst, int sum) {
	if (dep == n - 1) {
		ans = min(ans, sum);
		return;
	}
	for (int i = lst + 1; i <= m; i ++) {
		int u = find(U[i]), v = find(V[i]), w = W[i];
		if (u == v) continue;
		fa[u] = v;
		dfs(dep + 1, i, (sum + w) % k);
		fa[u] = u;
	}
}

signed main() {
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i ++) {
		cin >> U[i] >> V[i] >> W[i];
	}
	for (int i = 1; i <= n; i ++) fa[i] = i;
	dfs(0, 0, 0);
	cout << ans;
	return 0;
}