// baekjoon 1162 yechan
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<ll, pair<int,int> > P;

const int MAX_N=10001;
const int MAX_K=21;
const ll MAX_INF = (1LL << 62);

int N, M, K;
vector<pair<int,int> > adj[MAX_N];
ll dist[MAX_K][MAX_N];
bool visited[MAX_K][MAX_N];

int main() {
	scanf("%d%d%d", &N, &M, &K);
	for (int i=0; i<=K; i++)
		fill(dist[i], dist[i]+N+1, MAX_INF);

// 그래프를 구성할 edge 추가하기
	for (int i=0; i<M; i++) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back(make_pair(v, w));
		adj[v].push_back(make_pair(u, w));
	}

// 다익스트라 알고리즘
	priority_queue<P, vector<P>, greater<P> > PQ;
	PQ.push(make_pair(0,make_pair(K, 1)));
	dist[K][1] = 0;
	while (!PQ.empty()) {
		int cur_N, cur_K;
		do {
			cur_K = PQ.top().second.first;
			cur_N = PQ.top().second.second;
			PQ.pop();
		} while (!PQ.empty() && visited[cur_K][cur_N]);
		if (visited[cur_K][cur_N]) break;
		visited[cur_K][cur_N]=true;

		for (int i=0; i<adj[cur_N].size(); i++) {
			int next_N = adj[cur_N][i].first;
			ll next_W = adj[cur_N][i].second;
// 포장 할 수 있는 도로 개수가 남은 경우
			if (cur_K) {
// 도로를 포장하여 사용할때, 값이 업데이트 되는 지
				if (dist[cur_K-1][next_N] > dist[cur_K][cur_N]) {
					dist[cur_K-1][next_N] = dist[cur_K][cur_N];
					PQ.push(make_pair(dist[cur_K-1][next_N],make_pair(cur_K-1, next_N)));
				}
			}
// 기존 다익스트라 알고리즘 업데이트 형태
			if (dist[cur_K][next_N] > dist[cur_K][cur_N] + next_W) {
				dist[cur_K][next_N] = dist[cur_K][cur_N] + next_W;
				PQ.push(make_pair(dist[cur_K][next_N],make_pair(cur_K, next_N)));
			}
		}
	}

// 결과 출력
	ll ret = MAX_INF;
	for (int i=0; i<=K; i++)
		ret = min(ret, dist[i][N]);
	printf("%lld\n", ret);
	return 0;
}