#include<bits/stdc++.h>

using namespace std;
const int N=1e4,K=55,M=2e3+7;
struct side
{
	int nxt,to,value;
}edge[M];
struct smallheap
{
	int point,num,t;
}heap[N];
int n,m,k,head[N],distance1[N][K],cnt;
bool visit[N][K];
void addedge(int a,int b,int w)
{
	edge[++cnt].nxt=head[a];
	head[a]=cnt;
	edge[cnt].to=b;
	edge[cnt].value=w;
}
void heapinsert(int p,int numk,int pay,int heapsize)
{
	heap[heapsize].point=p;
	heap[heapsize].num=numk;
	heap[heapsize].t=pay;
	while(heap[heapsize].t<heap[heapsize>>1].t&&heapsize!=1)
	{
		swap(heap[heapsize],heap[heapsize>>1]);
		heapsize/=2;
	}
}
smallheap eject(int i,int heapsize)
{
	smallheap ans=heap[i];
	swap(heap[i],heap[heapsize--]);
	int l=i*2;
	while(l<=heapsize)
	{
		int best=l+1<=heapsize&&heap[l+1].t<heap[l].t?l+1:l;
		best=heap[best].t<heap[i].t?best:i;
		if(best==i)
		{
			break;
	    }
	    swap(heap[best],heap[i]);
	    i=best;
	    l=i*2;
	}
	return ans;
}
int main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		cin>>a>>b>>c;
		addedge(a,b,c);
		addedge(b,a,c);
	}
	int heapsize=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++)
		{
			distance1[i][j]=INT_MAX;
		}
	}
	distance1[1][0]=0;
	heapinsert(1,0,0,++heapsize);
	while(heapsize!=0)
	{
		smallheap x=eject(1,heapsize--);
	    if(visit[x.point][x.num])
	    {
			continue;
		}
		visit[x.point][x.num]=true;
		if(x.point==n)
		{
			cout<<x.t;
			return 0;
		}
		for(int i=head[x.point];i!=0;i=edge[i].nxt)
		{
			int v=edge[i].to,w=edge[i].value;
			if(x.num<k&&distance1[v][x.num+1]>distance1[x.point][x.num]+w/2)
			{
				distance1[v][x.num+1]=distance1[x.point][x.num]+w/2;
				heapinsert(v,x.num+1,distance1[v][x.num+1],++heapsize);
			}
			if(distance1[v][x.num]>distance1[x.point][x.num]+w)
			{
				distance1[v][x.num]=distance1[x.point][x.num]+w;
				heapinsert(v,x.num,distance1[v][x.num],++heapsize);
			}
		}
	}
}