#include<bits/stdc++.h>
using namespace std;
#define maxn 52
#define maxk 52
#define maxm 1003
#define mkp make_pair
int read(){
	int x=0;
	int f=1;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+(c^'0');
		c=getchar();
	}
	return x*f;
}
int n,m,k;
typedef pair<int,int> line;//first val,second id;
vector<line>g[maxn*maxk];
priority_queue<line,vector<line>,greater<line> >q;
bool vis[maxn*maxk];
int dis[maxn*maxk];
void dij(){
	n=n*(k+1);
//	cerr<<n<<endl;
	q.push(mkp(0,1));
	
	while(!q.empty()){
		int now=q.top().second;
		q.pop();
		if(vis[now])continue;
		vis[now]=1;
	//	cerr<<now<<endl;
//		for(int i=0;i<g[now].size();i++){
//			int to=g[now][i].second;
	//		cerr<<to<<' ';
//		}
		for(int i=0;i<g[now].size();i++){
			int to=g[now][i].second;
			//cerr<<to<<' ';
			if(dis[to]>dis[now]+g[now][i].first){
				dis[to]=dis[now]+g[now][i].first;
				q.push(mkp(dis[g[now][i].first],to));
			}
		}
	//	cerr<<endl;
	}
}
int main(){
	n=read();
	m=read();
	k=read();
	for(int i=1;i<=m;i++){
		int a,b,time;
		a=read();
		b=read();
		time=read();
		g[a].push_back(mkp(time,b));
		g[b].push_back(mkp(time,a));
		for(int i=1;i<=k;i++){
			g[a+i*n].push_back(mkp(time,b+i*n));
			g[a+(i-1)*n].push_back(mkp(time>>1,b+i*n));
			
			g[b+i*n].push_back(mkp(time,a+i*n));
			g[b+(i-1)*n].push_back(mkp(time>>1,a+i*n));
		}
	}
	memset(dis,0x3f,sizeof(dis));
	dis[1]=0;
	dij();
	int min_ans=0x7f7f7f7f;
	n=n/(k+1);
	for(int i=0;i<=k;i++){
		min_ans=min(min_ans,dis[i*n+n]);
	}
	cout<<min_ans;
	return 0;
}