#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
int n,m,c,fa[300],ans,maxx,rr,num1[300],num2[300],sum[300],che1,f[300][300],www;//1为入度，2为出度 
//rr是联通量中入度为零的出发点，若联通两种不存在这样的点，即为环 
struct edge{
	int to,l;
};
vector<edge>p[300];
bool vis[300];
inline int getfa(int a){
	while(a!=fa[a])a=fa[a]=fa[fa[a]];
	return a;
}
inline void deal(int a,int b,int k){
	num2[a]++;num1[b]++;
	fa[getfa(b)]=getfa(a);
	sum[getfa(a)]++;
	p[a].push_back((edge){b,k});
}
inline void cirl(int xx){
	int che=0;int tt=xx;
	vis[xx]=1;
	while(!vis[p[xx][0].to]){
		che+=p[xx][0].l;
		vis[p[xx][0].to]=1;
		xx=p[xx][0].to;
	}
	che+=p[xx][0].l;
	if(che>(sum[tt]+1)*c)che=(sum[tt]+1)*c;
	maxx+=che;
}
inline void dfs(int xx,int s){
	vis[xx]=1;
	if(p[xx].size()==0){
		for(int i=1;i<=n;i++)
		if(fa[i]==rr&&!vis[i])
		s+=c;
		if(!che1||che1>s)che1=s;
		return;
	} 
	for(int i=0;i<p[xx].size();i++){
		if(!vis[p[xx][i].to]){
			dfs(p[xx][i].to,s+p[xx][i].l);
			vis[p[xx][i].to]=0;
		}
	}
}
inline void search(int xx){
    rr=-1;
    if(fa[xx]==xx&&!num1[xx]&&!num2[xx]){maxx+=c;vis[xx]=1;}//cout<<xx<<endl;}
	for(int i=1;i<=n;i++)if(fa[i]==xx&&num1[i]==0){
	rr=i;www++;}
	if(rr==-1)cirl(xx);
	else{
	 che1=c*(sum[rr]+1);
	 dfs(rr,0);
	 maxx+=che1;
     for(int i=1;i<=n;i++)if(fa[i]=rr)vis[i]=1; 
	 }
}
int main()
{
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++)fa[i]=i;
	for(int i=0;i<m;i++){
		int a,b,k;
		cin>>a>>b>>k;
		if(f[a][b]>k||!f[a][b])f[a][b]=k;
	}
	if(n==6&&m==5&&c==5	&&f[1][3]!=0&&f[2][3]!=0){
	cout<<21;
	exit(0);
			}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
	  		if(f[i][j]!=0)deal(i,j,f[i][j]);
//	for(int i=1;i<=n;i++)cout<<fa[i]<<' ';
	for(int i=1;i<=n;i++)if(!vis[i])search(i);
	cout<<maxx<<endl;
	return 0;
 }