#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define int long long
int n,m,k,qi,zhong,w,ans,s,tmp,du[10],vis[30],di[10];
struct node{
	int qi,zhong,w;
}bian[30];
struct node1{
	int zhong,w;
};
queue<int>q;
vector <node1> v[10];
void check(){
	for(int i=1;i<=s;i++){
		if(!vis[i]){
			v[bian[i].qi].push_back({bian[i].zhong,bian[i].w});
		}
	}
	q.push(1);
	int sum=0;
	while(q.size()){
		int awa=q.front();
		q.pop();
		for(int i=0;i<v[awa].size();i++){
			if(!di[v[awa][i].zhong]){
				sum++;
				di[v[awa][i].zhong]=1;
				q.push(v[awa][i].zhong);
			}
		}
		if(sum==n){
			for(int i=1;i<=s;i++){
				if(!vis[i])
					ans+=bian[i].w;
			}
			ans%=k;
			tmp=min(ans,tmp);
			return;
		}
	}
	return;
}
void dfs(int num,int liang,int b){
	if(b==n+1)
		return ;
	if(num==liang){
		check();
		for(int i=1;i<=n;i++)
			di[i]=0;
		return ;
	}
	vis[b]=1;
	dfs(num+1,liang,b+1);
	vis[b]=0;
	dfs(num,liang,b+1);
	return ;
}
signed main(){
	cin>>n>>m>>k;
	tmp=k;
	while(m--){
		cin>>qi>>zhong>>w;
		s++;
		bian[s].qi=qi;
		bian[s].zhong=zhong;
		bian[s].w=w;
	}
	dfs(0,m-(n-1),1);
	cout<<tmp;
    return 0;
}


/*
       ┏┓　　　┏┓
     ┏┛┻━━━┛┻┓
     ┃　　　　　　　┃
     ┃　　　━　　　┃
     ┃　┳┛　┗┳　┃
     ┃　　　　　　　┃
     ┃　　　┻　　　┃
     ┃　　　　　　　┃
     ┗━┓　　　┏━┛Codes are far away from bugs with the animal protecting
         ┃　　　┃    神兽保佑,代码无bug
         ┃　　　┃
         ┃　　　┗━━━┓
         ┃　　　　　 ┣┓
         ┃　　　　 ┏┛
         ┗┓┓┏━┳┓┏┛
           ┃┫┫　┃┫┫
           ┗┻┛　┗┻┛     ○|￣|_

*/