#include <bits/stdc++.h>
using namespace std;
#define N 1000520
#define inf 0x3f3f3f

int n, m, k;
struct edge {
	int v, w;
};
int d[N], vis[N];
vector <edge> e[N];
priority_queue<pair<int, int> >q;

void dijkstra(int s) {
	for (int i = 1; i <= N; i++) d[i] = inf;//初始化要不止n个点，因为是分层图
	d[s] = 0;
	q.push({0, s});
	while (q.size()) {
		int u = q.top().second;
		q.pop();
		if (!vis[u]) {
			vis[u] = 1;
			for (auto x : e[u]) {
				int v = x.v, w = x.w;
				if (d[v] > d[u] + w) {
					d[v] = d[u] + w;
					q.push({-d[v], v});
				}
			}
		}
	}
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		e[a].push_back({b, c});
		e[b].push_back({a, c});
		for (int j = 1; j <= k; j++) {
			e[a + j*n].push_back({b + j*n, c});
			e[b + j*n].push_back({a + j*n, c});
			e[a + (j - 1)*n].push_back({b + j *n, c / 2});
			e[b + (j - 1)*n].push_back({a + j*n, c / 2});
		}
	}
	dijkstra(1);
	int ans = inf;
	for (int i = 0; i <= k; i++) {
		ans = min(ans, d[n + i*n]);
	}
	cout << ans;
	return 0;
}