rt

#include<bits/stdc++.h>
#define inf 0xffff
#define N 500005
#define int long long
using namespace std; 
int k,n,s,len,dis[N*21],t,sum,m,he[N*41],u,v,w,e1,ans=LONG_LONG_MAX;
struct nn{
	int n,w;
	bool operator < (const nn &B) const{
		return	B.w<w; 
	}
};
struct{
	int to,next,w,from;
}e[N*41];
void add(int x,int y,int z)
{
	sum++;
	e[sum].from=x;
	e[sum].w=z;
	e[sum].to=y;
	e[sum].next=he[x];
	he[x]=sum;
}
priority_queue<nn>q;
main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=n*k+n;i++){
		dis[i]=inf;
	} 
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w); 
		for(int j=1;j<=k
		;j++){
			add(u+(j-1)*n,v+j*n,0);
			add(v+(j-1)*n,u+j*n,0); 
			add(u+j*n,v+j*n,w);
			add(v+j*n,u+j*n,w); 
		}
	}
	for(int i=1;i<=k;i++){
        add(n+(i-1)*n,n+i*n,0);
    }
	dis[1]=0;
	q.push({1,0});
	while(!q.empty())
	{
		nn k=q.top();
		int xx=k.n;
		q.pop();
		for(int i=he[xx];i;i=e[i].next)
		{
			int to=e[i].to;
		//	cout<<d[to]<<" "<<e[to].w+k.w<<" "<<xx<<" "<<to<<endl;
			if(dis[to]>e[i].w+dis[xx])
			{		
				dis[to]=e[i].w+dis[xx];
				q.push({to,dis[to]});
			}
		}	
	}
	cout<<dis[n+n*k];
	return 0;
}