#include<bits/stdc++.h>
#define int long long
using namespace std;

typedef int lsqxx;
struct lq{
	lsqxx v,w,nxt;
}e[200005];
lsqxx h[200005],cnt;
void add(lsqxx u,lsqxx v,lsqxx w)
{
	e[++cnt].v=v,e[cnt].w=w,e[cnt].nxt=h[u],h[u]=cnt;
}

int n,m,k;
int x,y,z;
int ans[200005],vis[200005];
queue<int>q;
void spfa()
{
	while(!q.empty())
	{
		int x=q.front();q.pop();
		vis[x]=0;
		for(int i=h[x];i;i=e[i].nxt)
		{
			if(ans[x]+e[i].w<ans[e[i].v])
			{
				ans[e[i].v]=ans[x]+e[i].w;
				if(!vis[e[i].v]) vis[e[i].v]=1,q.push(e[i].v);
			}
		}
	}
}
signed main()
{
	cin>>n>>m>>k;
	memset(ans,0x7f,sizeof(ans));
	ans[1]=0;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&x,&y,&z);
		for(int ok=0;ok<=k;ok++)
			for(int oks=ok;oks<=k;oks++)
				if(ok==oks) add(x+ok*n,y+oks*n,z),add(y+ok*n,x+oks*n,z);
				else add(x+ok*n,y+oks*n,z/2),add(y+ok*n,x+oks*n,z/2);
	}
	q.push(1);
	spfa();
	int minx=0x7f7f7f7f;
	for(int i=0;i<=k;i++)
		minx=min(minx,ans[i*n+n]);
	cout<<minx<<endl;
    return 0;
}