#include<bits/stdc++.h>

using namespace std;

const int maxn=2147483647;

inline int read(){
	char ch=getchar();
	int x=0,f=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

int n,m,k;

struct node{
	int to,nxt,val;
}e[1000005];

int cnt,head[1000005];

void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	e[cnt].val=w;
	head[u]=cnt;
}

int dis[1000005];

bool vis[1000005];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;

void dijikstra(){
	for(int i=1;i<=n*(k+1);++i)dis[i]=maxn;
	dis[1]=0;
	q.push(make_pair(1,0));
	while(!q.empty()){
		int x=q.top().first;
		q.pop();
		if(vis[x]==1)continue;
		vis[x]=1;
		for(int i=head[x];i!=0;i=e[i].nxt){
			int tt=e[i].to,dd=e[i].val;
			if(dis[tt]>dis[x]+dd){
				dis[tt]=dis[x]+dd;
				q.push(make_pair(tt,dis[tt]));
			}
		}
	}
}

int main(){
	n=read(),m=read(),k=read();
	for(int i=1;i<=m;++i){
		int u=read(),v=read(),time=read();
//		add(u,v,time);
//		add(v,u,time);
		for(int j=0;j<=k;++j){
			add(u+n*j,v+n*j,time);
			add(v+n*j,u+n*j,time);
			add(u+n*(j-1),v+n*j,time/2);
			add(v+n*(j-1),u+n*j,time/2);
		}
	}
	dijikstra();
//	for(int i=1;i<=k+1;++i){
//		for(int j=1;j<=n;++j){
//			printf("%d ",dis[i*j]);
//		}
//		printf("\n");
//	}
//	printf("%d",dis[n*(k+1)]);
	int minn=maxn;
	for(int i=0;i<=k;++i){
		minn=min(minn,dis[n+n*i]);
	}
	printf("%d",minn);
	return 0;
}