#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef unsigned long long ull;

const ll INF = (1ll << 62);

#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;
}

const int N = 100 + 5;
const int K = 1e3 + 5;

#define int ll

int n, m, k, ans, g[N][N], f[N][N][K];

signed main() {
	read(n); read(m); read(k);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			g[i][j] = INF;
			for(int l = 0; l <= k; l++) {
				f[i][j][l] = INF;
				f[i][i][l] = 0;
			}
		}
		g[i][i] = 0;
	}
	for(int i = 1, u, v, w; i <= m; i++) {
		read(u); read(v); read(w);
		u -- ; v -- ;
		g[u][v] = min(g[u][v], w);
	}
	for(int l = 0; l <= k; l++) {
		for(int k = 0; k < n; k++) {
			for(int i = 0; i < n; i++) {
				for(int j = 0; j < n; j++) {
					if(i == j) continue;
					if(g[k][j] == INF) continue;
					if(f[i][k][l] != INF) f[i][j][l] = min(f[i][j][l], f[i][k][l] + g[k][j]);
					if(l >= 1 && f[i][k][l - 1] != INF) f[i][j][l] = min(f[i][j][l], f[i][k][l - 1] - g[k][j]);
				}	
			}
		}
	}
	ans = INF;
	for(int i = 0; i <= k; i++) ans = min(ans, f[0][n - 1][i]);
	cout << ans << endl;
	return 0;
}