#3 TLE && #6 WA

#include<bits/stdc++.h>
#define gc() getchar()
#define reg register
using namespace std;
typedef long long ll;
inline ll read(){
	reg ll res=0,k=1;
	reg char ch = gc();
	while(ch < '0'||ch > '9'){
		if(ch == '-')k=-1;
		ch = gc();
	}
	while(ch >= '0'&&ch <= '9'){
		res = res*10+ch-'0';
		ch = gc();
	}
	return res*k;
}

int n, m, k;
struct edge{int s, e, v, next;}eg[1005 * 2];
int head[55];
int cnt;
inline void make(reg int s, reg int e, reg int v){
	eg[++cnt] = {s, e, v, head[s]};
	head[s] = cnt;
}

ll dis[55][55];

inline void dfs(reg int id, reg int use, reg int step){
	if(step >= dis[id][use])return;
	dis[id][use] = step;
	for(reg int i = head[id] ; i ; i = eg[i].next){
		dfs(eg[i].e, use, dis[id][use] + eg[i].v);
		if(use + 1 <= k)dfs(eg[i].e, use + 1 , dis[id][use] + eg[i].v/2);
	}
}

struct Node{int id, use, step;};
inline void bfs(){
	dis[1][0] = 0;
	queue <Node> q;
	q.push((Node){1, 0, 0});
	while(!q.empty()){
		Node t = q.front();
		q.pop();
		for(reg int i = head[t.id] ; i ; i = eg[i].next){
			if(t.step + eg[i].v < dis[eg[i].e][t.use]){
				dis[eg[i].e][t.use] = t.step + eg[i].v;
				q.push((Node){eg[i].e, t.use, dis[eg[i].e][t.use]});
			}
			if(t.use + 1 <= k && t.step + eg[i].v / 2 < dis[eg[i].e][t.use + 1]){
				dis[eg[i].e][t.use + 1] = t.step + eg[i].v / 2;
				q.push((Node){eg[i].e, t.use + 1, dis[eg[i].e][t.use + 1]});
			}
		}
	}
}

int main(){
	memset(dis, 0x7f, sizeof(dis));
	n = read(), m = read(), k = read();
	for(reg int i = 1 ; i <= m ; ++i){
		reg int s = read(), e = read(), v = read();
		make(s, e, v);
		make(e, s, v);
	}
	bfs();
   //dfs(1, 0, 0)
	ll ans = 0x7fffffff;
	for(int i = 0 ; i <= k ; ++i)
		ans = min(ans,dis[n][i]);
	printf("%lld\n", ans);
	return 0;
}