#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int maxn = 300;
const int maxm = 30000 + 100;
int n, c, m;
int g[maxn][maxn], gq[maxn][maxn];
int minm = 0;
int b[maxn];

struct node
{
	int s;
	int t;
	int v;
}r[maxn];

int fun(int x, int y)
{
	if (g[x][y] == 1 && b[y] == 0)
	{
		minm += gq[x][y];
		b[y] = 1;
		x = y;
		int minq = 10001;
		int f;
		for(int i = 1; i <= n; i++)
		{
			if (g[y][i] == 1 && gq[y][i] < minq)
			{
				minq = gq[y][i];
				f = i;
			}
		}
		y = f;
		fun(x, y);
	}
	else 
		return minm;
}

int main()
{
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	memset(g,0,sizeof(g));
	memset(b,0,sizeof(b));
	cin >> n >> m >> c;
	for (int i = 1; i <= m; i++)
	{
		cin >> r[i].s >> r[i].t >> r[i].v;
		g[r[i].s][r[i].t] = 1;
		gq[r[i].s][r[i].t] = r[i].v;
	}
	for (int i = 1;i < n; i++)
		for (int j = i+1; j <= n; j++)
			minm = fun(i,j);
	int minx = 10001;
	for (int i = 1; i <= n; i++)
		if (b[i] == 0)
		{
			minm += c;
			break;
		}
	cout << minm;
	return 0;
}