#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<queue>
#include<ctime>
#include<cstdlib>
using namespace std;

int n=0,m=0,c=0;
long long ans=0;
bool f[300]={};

struct hehe{
	int y,next,v;
};
hehe e[30010];
int linkk[300]={},len=0;

void insert(int s,int t,int vv){
	e[++len].next=linkk[s];
	linkk[s]=len;
	e[len].y=t;
	e[len].v=vv;
}
void init(){
	scanf("%d%d%d",&n,&m,&c);
	int s=0,t=0,vv=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&s,&t,&vv);
		insert(s,t,vv);
	}
	ans=1LL*c*n;
}
void dfs(int k,int last,int num,int sum){
	sum+=e[last].v;
	if(sum<ans)	ans=sum;
	if(num==n || f[k])	return ;
	f[k]=true;
	for(int i=linkk[k];i;i=e[i].next)
	{
		if(i!=last)
		{
			dfs(e[i].y,i,num+1,sum-c);//动能弹经过这个点至下一个点
			dfs(e[i].y,i,num+1,sum-e[last].v);//动能弹由这个点发射
		}
	}
}
int main(){
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	
	init();
	if(n<=10)
	{
		dfs(1,0,0,c*n);
		cout<<ans<<endl;
	}
	else	cout<<ans<<endl;
	
	fclose(stdin);fclose(stdout);
	return 0;
}