#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=3e6;
int read()
{
int sum=0;char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch<='9'&&ch>='0')
{
sum=sum*10+ch-'0';
ch=getchar();
}
return sum;
}
int n,m,k,dis[2*maxn],cnt,v[maxn];
int head[2*maxn],nxt[2*maxn],to[2*maxn],w[2*maxn];
void add(int x,int y,int z)
{
cnt++;nxt[cnt]=head[x];head[x]=cnt;to[cnt]=y;w[cnt]=z;
}
priority_queue<pair<int ,int > >q;
void dijstra()
{
memset(dis,0x3f,sizeof(dis));
memset(v,0,sizeof(v));
dis[1]=0;q.push(make_pair(0,1));
while(!q.empty())
{
int x=q.top().second;q.pop();
if(v[x]) continue; v[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i],z=w[i];
if(dis[y]>dis[x]+z)
{
dis[y]=dis[x]+z;
q.push(make_pair(-dis[y],y));
}
}
}
}
int main()
{
n=read();m=read();k=read();
for(int x,y,z,i=1;i<=m;i++)
{
x=read();y=read();z=read();
for(int j=0;j<=k;j++)
{
add(x+j*n,y+j*n,z);
add(y+j*n,x+j*n,z);
if(j!=k)
{
add(x+j*n,y+(j+1)*n,0);
add(y+j*n,x+(j+1)*n,0);
}
}
}
dijstra();
int ans=2147483640;
for(int i=0;i<=k;i++)
ans=min(ans,dis[n+i*n]);
cout<<ans;
return 0;
}
