#include <bits/stdc++.h>
using namespace std;
const int maxn=20010,maxm=50010;
long long n,m,k,cnt;
long long head[100*maxn],dis[100*maxn];
bool vis[100*maxn];
struct poi
{
	int pos,v;
	bool operator < (const poi &x)const
	{
		return x.v<v;
	}
};
struct edge
{
	long long t,w,next;
}e[200*maxm];
inline void add(int f,int t,int w)
{
	e[++cnt].t=t;
	e[cnt].w=w;
	e[cnt].next=head[f];
	head[f]=cnt;
}
void dij()
{
	priority_queue<poi> q;
	q.push((poi){1,0});
	for(int i=1;i<=33*n;i++)
	dis[i]=0x7fffffff;
	memset(vis,false,sizeof(vis));
	dis[1]=0;
	while(q.size())
	{
		int x=q.top().pos;
		q.pop();
		if(vis[x])continue;
		vis[x]=true;
		for(int i=head[x];i;i=e[i].next)
		{
			int y=e[i].t,v=e[i].w;
			if(dis[y]>dis[x]+v)
			{
				dis[y]=dis[x]+v;
				if(!vis[y])
				q.push((poi){y,dis[y]});
			}
	    }
	}
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
		for(int j=1;j<=k;j++)
		{
			add(u+n*j,v+n*j,w);
			add(v+n*j,u+n*j,w);
			add(v+(j-1)*n,u+j*n,w/2);
			add(u+(j-1)*n,v+j*n,w/2);
		}
	}
	dij();
	long long ans=dis[n];
	for(int i=1;i<=k;i++)
	ans=min(ans,dis[i*n+n]);
	cout<<ans;
}