#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int maxm = 30;
const int maxn = 1 << 8;
struct edge
{
	int to,nxt,w;
}e[maxm << 1];
int head[maxm],tot;
void add_edge(int u,int v,int w)
{
	e[++tot].nxt = head[u];
	head[u] = tot;
	e[tot].to = v;
	e[tot].w = w;
}
int n,m,K;
int dp[maxn];
signed main()
{
	cin >> n >> m >> K;
	for(int i = 1;i <= m;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		u--;
		v--;
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	memset(dp,63,sizeof(dp));
	const int maxx = dp[0];
	for(int i = 0;i < n;i++)
	{
		dp[1 << i] = 0;
	}
	for(int i = 1;i < 1 << n;i++)
	{
		for(int k = 0;k < n;k++)
		{
			if(i & (1 << k))
			{
				int S = i - (1 << k);
				for(int j = head[k];j;j = e[j].nxt)
				{
					int v = e[j].to;
					if(i & (1 << v))
					{
						if(dp[S] == maxx)
						{
							continue;
						}
						int res = (dp[S] + e[j].w) % K;
						dp[i] = min(dp[i],res);
					}
				}
			}
		}
	}
	cout << dp[(1 << n) - 1];
	return 0;
}

写了一个状压