#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <queue>

using namespace std;

template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}

typedef long long ll;
typedef unsigned long long ull;

const int INF = 1e9;

#define DEBUG(x) std::cerr << #x << " = " << x << std::endl

template <typename T> void read (T &x) {
    x = 0; bool f = 1; char ch;
    do {ch = getchar(); if (ch == '-') f = 0;} while (ch > '9' || ch < '0');
    do {x = x * 10 + ch - '0'; ch = getchar();} while (ch >= '0' && ch <= '9');
    x = f ? x : -x;
}

template <typename T> void write (T x) {
    if (x < 0) x = ~x + 1, putchar ('-');
    if (x > 9) write (x / 10);
    putchar (x % 10 + '0');
}

const int N = 100 + 5;
const int M = 2500 + 5;
const int K = 1e6 + 5;

#define int ll

struct EDGE {
	int u, v, w;
} edge[M];

int n, m, kk, g[N][N];

struct Matrix {
	int num[N][N];
	inline void init() {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				num[i][j] = INF;
			}
		}
	}
	inline void print() {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				printf("%lld ", num[i][j]);
			}
			puts("");
		}
	}
	Matrix operator *(const Matrix &b) const {
		Matrix c; c.init();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				for(int k = 0; k < n; k++) {
					if(num[i][k] == INF || b.num[k][j] == INF) continue;
					c.num[i][j] = min(c.num[i][j], num[i][k] + b.num[k][j]);
				}
			}
		}
		return c;
	}
} base, ans;

inline void qpow(int b) {
	// ans.print();
	// base.print();
	while(b) {
		if(b & 1) ans = ans * base;
		base = base * base;
		b >>= 1;
	}
}

signed main() {
	read(n); read(m); read(kk);
	memset(g, 63, sizeof(g));
	for(int i = 0; i < n; i++) g[i][i] = 0;
	for(int i = 1; i <= m; i++) {
		read(edge[i].u); read(edge[i].v); read(edge[i].w);
		edge[i].u -- ; edge[i].v -- ;
		g[edge[i].u][edge[i].v] = edge[i].w;
	}
	for(int k = 0; k < n; k++) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
			}
		}
	}
	if(kk) {
		for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) base.num[i][j] = INF, ans.num[i][j] = g[i][j]	;
		for(int i = 0; i < n; i++) base.num[i][i] = 0;
		for(int i = 1; i <= m; i++) {
			int u = edge[i].u, v = edge[i].v, w = edge[i].w;
			for(int j = 0; j < n; j++) {
				for(int k = 0; k < n; k++) {
					if(g[j][u] == INF || g[v][k] == INF) continue;
					chkmin(base.num[j][k], min(g[j][k], g[j][u] - w + g[v][k]));
				}
			}
		}
		qpow(kk - 1);

		printf("%lld\n", base.num[0][n - 1]);
	} else {
		printf("%lld\n", g[0][n - 1]);
	}
	return 0;
}