#include<bits/stdc++.h>
#define int long long
using namespace std;
long long f[101][101];
int u[2501], v[2501], c[2501];
int n, m, k;
template<class Type, int nn, int mm>
class matrix {
	public:
		Type val[nn + 3][mm + 3];
		int n, m;
		void setnm(int n, int m){
			this->n = n, this->m = m;
		}
		void read(int n, int m) {
			this->n = n, this->m = m;
			for (register int i = 1; i <= n; i++)
				for (register int j = 1; j <= m; j++)
					std::cin >> this->val[i][j];
		}
		void print() {
			for (register int i = 1; i <= n; i++) {
				for (register int j = 1; j <= m; j++) 
					std::cout << this->val[i][j] << " ";
				std::cout << "\n";
			}
		}
		matrix operator -() {
			matrix<Type, nn, mm> tmp;
			for (register int i = 1; i <= n; i++)
				for (register int j = 1; j <= m; j++)
					tmp.val[i][j] = -(this->val[i][j]);
			return tmp;
		}
		matrix operator +(matrix b) {
			matrix<Type, nn, mm> tmp;
			for (register int i = 1; i <= n; i++)
				for (register int j = 1; j <= m; j++)
					tmp.val[i][j] = (this->val[i][j] + b.val[i][j]);
			return tmp;
		}
		matrix operator =(matrix b) {
			for (register int i = 1; i <= n; i++)
				for (register int j = 1; j <= m; j++)this->val[i][j] = b.val[i][j];
			return b;
		}
		matrix operator +=(matrix b) {
			(*this) = (*this) + b;
			return (*this);
		}
		matrix operator -(matrix b) {
			return (*this) + (-b);
		}
		matrix operator -=(matrix b) {
			(*this) = (*this) - b;
			return (*this);
		}
		matrix operator *(matrix b) {
			matrix<Type,nn,mm> res;
			res.m = res.n = this->n;
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					res.val[i][j] = 100000000000000ll;
			for (register int k = 1; k <= n; k++)
				for (register int i = 1; i <= n; i++)
					for (register int j = 1; j <= n; j++)
						if (res.val[i][j] > this->val[i][k] + b.val[k][j])
							res.val[i][j] = this->val[i][k] + b.val[k][j];
			return res;
		}
		matrix operator *=(matrix b) {
			(*this) = (*this) * b;
			return (*this);
		}
		matrix operator ^(long long k) {
			matrix<Type, nn, mm> qwq, qaq = (*this);
			qwq.n = this->n;
			for (int i = 1; i <= qwq.n; i++)
				for (int j = 1; j <= qwq.n; j++)
					qwq.val[i][j] = f[i][j];
			while (k){
				if (k & 1)
					qwq = (qwq * qaq);
				qaq = (qaq * qaq);
				k >>= 1;
			}
			return qwq;
		}
		matrix operator ^=(long long b) {
			(*this) = (*this) ^ b;
			return (*this);
		}
};
matrix<long long, 101, 101> x;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0); 
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			f[i][j] = 1000000000000000ll;
	for (int i = 1; i <= m; i++){
		cin >> u[i] >> v[i] >> c[i];
		f[u[i]][v[i]] = c[i];
	}
	for (int kk = 1; kk <= n; kk++)
		for (int i = 1; i <= n; i++)	
			for (int j = 1; j <= n; j++)
				if (f[i][j] > f[i][kk] + f[kk][j])
					f[i][j] = f[i][kk] + f[kk][j];
	for (int i = 1; i <= n; i++)
		f[i][i] = 0;
	if (k == 0){
		cout << f[1][n];
		exit(0);
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			x.val[i][j] = f[i][j];
	x.setnm(n, n);
	for (int kk = 1; kk <= m; kk++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (x.val[i][j] > f[i][u[kk]] + f[v[kk]][j] - c[kk])
					x.val[i][j] = f[i][u[kk]] + f[v[kk]][j] - c[kk];
//	for (int i = 1; i <= n; i++)
//		for (int j = 1; j <= n; j++)
	//		cout << i << " " << j << " " << x.val[i][j] << "\n";
	cout << (x ^ k).val[1][n];
}