#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
int n,m,c,sum,ans,maxn;
struct edge{
	int v,y,next;
}e[30100];int lin[300],len;
bool flag[300];
void dfs(int s){
	if(s==maxn){
		for(int i=1;i<=n;i++){
			if(flag[i]==0)
				ans+=c;
		}
		int minn=min(n*c,ans);
		cout<<minn<<endl;
	}
	int st=lin[s];
	for(int i=st;i;i=e[i].next){
		int poi=e[i].y;
		if(flag[poi]==0){
			flag[poi]=1;ans+=e[i].v;
			dfs(poi);
			flag[poi]=0;ans-=e[i].v;
		}
	}
}
void in(int xx,int yy ,int vv){
	e[++len].next=lin[xx];
	lin[xx]=len;
	e[len].y=yy;
	e[len].v=vv;
}
int main(){
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	scanf("%d%d%d",&n,&m,&c);
	for(int i=1;i<=m;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		in(x,y,z);
		maxn=max(maxn,max(x,y));
	}
	dfs(1);
	return 0;
}