rt

#include <bits/stdc++.h>
#define pll std::pair <LL, LL> 
#define mp std::make_pair 

typedef long long LL;
LL n, m, k, s, t;
const int N = 2e6 + 5;
LL head[N], tail[N], nxt[N], value[N], tot;
inline void add_edge (LL u, LL v, LL val) {
	tail[++tot] = v;
	nxt[tot] = head[u];
	value[tot] = val;
	head[u] = tot;
}
LL dist[N];
bool vis[N];
std::priority_queue <pll, std::vector <pll>, std::greater <pll> >q;
inline void Dijsktra() {
	memset (dist, 0x3f, sizeof(dist));
	dist[1] = 0;
	q.push(mp(dist[1], 1));
	while (!q.empty()) {
		LL u = q.top().second; q.pop();
		if (vis[u] == 1) continue;
		vis[u] = 1;
		for (LL i = head[u]; i; i = nxt[i]) {
			LL ed = tail[i], v = value[i];
			if (dist[ed] > dist[u] + v) {
				dist[ed] = dist[u] + v;
				q.push(mp(dist[ed],ed));
			}
		}
	}
}
int main() {
	std::cin >> n >> m >> k;
	while (m--) {
		LL u, v, val;
		std::cin >> u >> v >> val;
		add_edge (u, v, val);
		add_edge (v, u, val);
		for (LL i = 1; i <= k; ++i) {
			add_edge (u + n * (i - 1), v + n * i, 0);
			add_edge (v + n * (i - 1), u + n * i, 0);
			add_edge (u + i * n, v + i * n, val);
			add_edge (v + i * n, u + i * n, val);
		}
	}
	Dijsktra();
	LL ans = INT_MAX;
	for (LL i = 0; i <= k; ++i) ans = std::min (ans, dist[n + i * n]);
	std::cout << ans;
	return 0;
}