#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e4+4;
const int M=5e4+4;
const int K=25;
const int SW=7e7+7;
const long long INF=0x3f3f3f3f3f3f3f3f;
int n,m,k,h[SW],vis[SW];
long long dis[SW],tot;
struct sw{
	int v,w,nxt;
}e[SW];
struct WS{
	int num;
	long long dist;
	bool operator <(const WS c)const{
		return dist>c.dist;
	}
};
priority_queue<WS> q;
void add(int u,int v,int w){
	//cout<<"u="<<u<<" v="<<v<<" w="<<w<<endl;
	tot++;
	e[tot].v=v;
	e[tot].w=w;
	e[tot].nxt=h[u];
	h[u]=tot;
	//cout<<"正常"<<endl;
}
void dij(){
	for(int i=1;i<=k*n+n;i++){
		dis[i]=INF;
	}
	dis[1]=0;
	q.push((WS){1,0});
	while(!q.empty()){
		int s=q.top().num;q.pop();
		if(vis[s]) continue;
		vis[s]=1;
		for(int i=h[s];i;i=e[i].nxt){
			int v=e[i].v;
			if(!vis[v]&&dis[v]>dis[s]+e[i].w){
				dis[v]=dis[s]+e[i].w;
				q.push((WS){v,dis[v]});
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&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=0;j<=k;j++){
			add(j*n+u,j*n+v,w);
			add(j*n+v,j*n+u,w);
		}
		for(int j=0;j<k;j++){
			add(j*n+u,(j+1)*n+v,0);
		}
	}
	dij();
	long long mi=INF;
	for(int i=0;i<=k;i++){
		//cout<<"!!!"<<endl;
		mi=min(mi,dis[i*n+n]);
	}
	printf("%lld",mi);
	return 0;
}