/*
Problem:cogs2084;
Language:c++;
by dydxh;
2015.11.03;
*/
#include<iostream>
#include<cstdio>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<utility>
#include<ctime>
#include<cstdlib>
#include<bitset>
#include<string>
#define ll long long
#define ull unsigned long long
using namespace std;
const int oo=2000000000;
const int maxn=255;
int n,m,C,ans,now;
int maps[maxn][maxn],Col[maxn],Head[maxn];
inline int read(){
	int x=0;bool flag=0;char ch=getchar();
	while(ch>'9' || ch<'0') {if(ch=='-') flag=1;ch=getchar();}
	while(ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
	return flag?-x:x;
}
inline int Judge(){
	int num=0;
	for(int i=1;i<=n;i++)
		if(Col[i]==-1)
			num++;
	return num;
}
void Dfs(int x,int Color){
	if(now>ans) return ;
	int num=Judge();
	if(now+num*C<ans) ans=now+num*C;
	if(num==0) return ;
	if(Col[x]==Color){  //circle;
		if(Head[Color]!=x) return ;
		for(int i=1;i<=n;i++)
			if(Col[i]==-1){
				Head[Color+1]=i;
				Dfs(i,Color+1);
				Col[i]=-1;
				Head[Color+1]=-1;
			}
		return ;
	}
	Col[x]=Color;
	for(int i=1;i<=n;i++){  //line
		if(maps[x][i]){
			if(Col[i]!=-1 && Col[i]!=Color) continue;
			now+=maps[x][i];
			Dfs(i,Color);
			now-=maps[x][i];
			Col[i]=-1;
		}
	}
	now+=C;
	for(int i=1;i<=n;i++)
		if(Col[i]==-1){
			Head[Color+1]=i;
			Dfs(i,Color+1);
			Col[i]=-1;
			Head[Color+1]=-1;
		}
	now-=C;
}
int main()
{
	//freopen("cc.in","r",stdin);
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	n=read(),m=read(),C=read();
	for(int i=1;i<=m;i++){
		int x=read(),y=read();
		maps[x][y]=read();
	}
	ans=C*n;
	for(int i=1;i<=n;i++){
		memset(Col,-1,sizeof(Col));
		memset(Head,-1,sizeof(Head));
		now=0;
		Head[1]=i;
		Dfs(i,1);
	}
	printf("%d\n",ans);
	return 0;
}