#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;
#define MAXN (260)

/*
int indge[MAXN];
int outdge[MAXN];
bool alive[MAXN];
*/

int graph[MAXN][MAXN];

int N,M,C;
struct node
{
	vector<int> adj;
	int indge;
	int outdge;
	bool alive;
	bool nvis;
	node()
	{
		indge = 0;
		outdge = 0;
		alive = false;
		nvis = true;
		adj.clear();
	}
};

node ns[MAXN];
int ans[MAXN];

void set_file()
{
	freopen("asm_lis.in", "r", stdin);
	freopen("asm_lis.out", "w", stdout);
}
int y = 0;
void read()
{
	int i;
	int u,v,t;
	scanf("%d %d %d", &N, &M, &C);
	for(i = 1; i <= M; i++)
	{
		scanf("%d %d %d", &u, &v, &t);
		graph[u][v] = t;
		y += t;
		ns[u].adj.push_back(v);
		ns[u].outdge++;
		ns[v].indge++;
		ns[u].alive = true;
		ns[v].alive = true;
		
		/*
		outdge[u]++;
		indge[v]++;
		alive[u] = true;
		alive[v] = true;
		*/
	}
}

/*
void solve(int fm)
{
	int i,j,k,l,m,n,t,u,v;
	int cost = 0;
	stack<int> stk;            //用于记录 
	m = 0x7fffffff;
	
	//开始深搜 
	stk.push(fm);
	while(!stk.empty())
	{
		k = stk.top();
		stk.pop();
		
		for(i = 0; i < ns[k].adj.size(); i++)
		{
			j = ns[k].adj[i];
			if(!ns[j].alive)continue;
			stk.push(j);
		}
	}
	
	
	u = 0;
	for(i = 1; i <= N; i++)    //枚举所有节点 
	{
		k = i;   //k = 当前正在使用的节点 
		for(j = 0; j < ns[k].adj.size(); j++)           //枚举当前节点的子节点 
		{
			l = ns[k].adj[j];
			stk.push(l);				
		}
		for(j = 0; j < ns[k].adj.size(); j++)           //枚举当前节点的子节点 
		{
			l = ns[k].adj[j];
			u += graph[k][l];
			if(ns[l].outdge)k = l;
			else
			{
				k = stk.top();
				stk.pop();
			}				
		}
	}
	
}
*/

int r = 0x7ffffff;
int st;
void dfs(int nd, int ct)
{
	if(ns[nd].outdge == 0)
	{
		r = min(r, ct);
		return;		
	}else if(st==nd && !ns[nd].nvis)
	{
		r = min(r, ct);
		return;
	}else
	{
		ns[nd].nvis = false;
		for(int i = 0; i < ns[nd].adj.size(); i++)
		{
			int q = ns[nd].adj[i];
			if(ns[q].alive)
			{
				ns[q].alive = false;
				ns[q].nvis = false;
				dfs(q, ct+graph[nd][q]);
				ns[q].alive = true;
			}
		}
	}
}

int main()
{
	set_file();
	memset(graph, 0, sizeof(graph));
	int k,i,j,t;
	int res = 0x7fffffff;
	read();
	for(i = 1; i <= N; i++)
	{
		st = i;
		dfs(i, 0);
		t = r;
		for(j = 1; j <= N; j++)
		{
			r = 0x7fffffff;
			if(ns[j].nvis)
			{
				if(!ns[j].outdge && !ns[j].indge)
				{
					t += C;	
				}else
				{
					r = 0x7fffffff;
					st = j;
					dfs(j, 0);
					t += r;
					j = 1;
				}
				r = 0x7fffffff;
			}
		}
		res = min(res, t);
		ns[j].nvis = true;
		ns[j].alive = true;
	}
	cout << res+y << endl;
	return 0;
}