rt

#include<bits/stdc++.h>
#define qwert std::cout<<"\n"
#define asdf std::cout<<" "

inline int read(){
   	int s=0;
   	int w=1;
   	char ch=getchar();
   	for(;ch<'0'||ch>'9';ch=getchar())
    	if(ch=='-')
			w=-1;
   	for(;ch>='0'&&ch<='9';ch=getchar())
		s=s*10+ch-'0';
   	return s*w;
}

void write(int x) {
	if(x<0){
    	putchar('-');
    	x=-x;
  	}
  	if(x>9)
    	write(x/10);
	putchar(x%10+'0');
	return;
}
class ed{
	public:
		int u;
		int v;
		int w;
}e[10000086];
int dis[5000086];
bool vis[5000086];
int head[5000086];
int point;
int n,m,k;
std::priority_queue<std::pair<int,int> >q;
void add(int u,int v,int w){
	e[++point]=(ed){v,head[u],w};
    head[u]=point;
}
void dij(int s){//dij模板
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	q.push(std::make_pair(0,s));
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		if(vis[x])
			continue;
		vis[x]=true;
		for(int i=head[x];i;i=e[i].v){
			int y=e[i].u;
			if(dis[x]+e[i].w<dis[y]){
				dis[y]=dis[x]+e[i].w;
				q.push(std::make_pair(-dis[y],y));
			}
		}
	}
}
int main(){
	n=read();
	m=read();
	k=read();
	for(int i=1;i<=m;i++){
		int u=read();
		int v=read();
		int w=read();
		add(u,v,w);
		add(v,u,w);
		for(int j=1;j<=k;j++){
			add(u+(j-1)*n,v+j*n,w/2);
            add(v+(j-1)*n,u+j*n,w/2);
            add(u+j*n,v+j*n,w);
            add(v+j*n,u+j*n,w);
        }//分层图
	}
	dij(1);
	write(dis[n+k*n]);
	return 0;
}