#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<stdio.h>
#include<cstdlib>
#include<iomanip>	//cout<<setiosflags(ios::fixed)<<setprecision(2);
#include<ctime> //double a=(double)clock();	cout<<a<<endl;
#include<vector>
#include<queue>
using namespace std;
inline int read()
{
	int x=0,ff=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
	return ff*x;
}
int N,M,C,t1,t2,t,ans=1<<30;
int e[251][251],num[251];
int main()
{
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	memset(e,10,sizeof(e));
	N=read(),M=read(),C=read();
	for(int i=1;i<=M;i++)
	{
		t1=read(),t2=read(),t=read();
		t=min(t,C);
		e[t1][t2]=min(e[t1][t2],t);
	}
	for(int i=1;i<=N;i++)
		num[i]=i;
	do
	{
		int j,sum=0,tsum;
		for(int i=1;i<=N;)
		{
			if(e[num[i]][num[i+1]]!=e[0][0])
			{
				j=i,tsum=0;
				while(e[num[j]][num[j+1]]!=e[0][0])
					tsum+=e[num[j]][num[j+1]],j++;
				if(e[num[j]][num[i]]!=e[0][0])
					tsum+=e[num[j]][num[i]]-C;
				tsum=min(tsum,C*(j-i));
				sum+=tsum,i=j;
			}
			else
				sum+=C,i++;
		}
		ans=min(ans,sum);
		if(clock()>=3900)
		{
			printf("%d\n",ans);
			return 0;
		}
	}while(next_permutation(num+1,num+1+N));
	printf("%d\n",ans);
	return 0;
}