#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define p pair<long long,int>
#define mp make_pair
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define rop(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define por(i,a,b) for(int i=(a);i>(b);i--)
using namespace std;

const int N=1e6+10;

priority_queue<p,vector<p>,greater<p> > q;
int n,m,k,cnt,h[N];
long long dis[N<<2];
bool vis[N<<2];
struct node{
	int nx,to;
	long long w;
}e[N<<2];

void add(int a,int b,long long c){
	e[++cnt].nx=h[a]; e[cnt].to=b; e[cnt].w=c; h[a]=cnt;
}

void dj(int s){
	memset(dis,0x3f,sizeof dis);
	dis[s]=0;
	q.push(mp(0,s));
	while(q.size()){
		int x=q.top().second;
		int v=q.top().first;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;  dis[x]=v;
		for(int i=h[x];i;i=e[i].nx){
			int y=e[i].to;
			if(vis[y]) continue;
			dis[y]=min(dis[y],dis[x]+e[i].w);
			q.push(mp(dis[y],y));
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&k);
	while(m--){
		int a,b;
		long long c;
		scanf("%d%d%lld",&a,&b,&c);
		add(a,b,c); add(b,a,c);
		rep(i,1,k){
			add(a+(i-1)*n,b+i*n,0);
			add(b+(i-1)*n,a+i*n,0);
			add(a+i*n,b+i*n,c);
			add(b+i*n,a+i*n,c);
		}
	}
	rep(i,1,k){
		add(n+n*(i-1),n+n*i,0);
	}
	dj(1);
	printf("%lld",dis[n+n*k]);	
	return 0;
}