#include<set>
#include<list>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
#define min(a,b) a<b?a:b
inline int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
		s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s*w;
}
inline void write(int x) {
	if(x>9)	write(x/10);
	putchar(x%10+'0');
}
inline void print(int x,char ch='\n') {
	if(x<0)putchar('-');
	write(__builtin_labs(x));
	putchar(ch);
}
int n=read(),m=read(),k=read(),cnt;
int head[200001],Next[200001],ver[200001],edge[200001];
int d[5001],need[5001];
bool v[5001];
void add(int z,int y,int x) {
	ver[++cnt]=y;
	edge[cnt]=z;
	Next[cnt]=head[x];
	head[x]=cnt;
	ver[++cnt]=x;
	edge[cnt]=z;
	Next[cnt]=head[y];
	head[y]=cnt;
}
priority_queue<pair<int,int> >q;
inline void dij() {
	memset(d,0x3f,sizeof(d));
	memset(need,0x3f,sizeof(need));
	q.push(make_pair(0,1));
	d[1]=0;
	while(!q.empty()) {
		int x=q.top().second,w=-q.top().first,sum=0;
		q.pop();
		for(int i=head[x]; i; i=Next[i])if(ver[i]!=x)sum++;
		if(sum<k&&x!=n&&x!=1)continue;
		for(int i=head[x]; i; i=Next[i])
			if(ver[i]!=x) {
				int y=ver[i],z=edge[i];
				if(d[y]>w+z) {
					need[y]=d[y],d[y]=w+z;
					q.push(make_pair(-d[y],y));
					q.push(make_pair(-need[y],y));
				} else if(need[y]>w+z)
					need[y]=w+z,q.push(make_pair(-need[y],y));
			}
	}
}
signed main() {
	for(int i=1; i<=m; i++)add(read(),read(),read());
	dij();
	print(need[n]>=0x3f3f3f3f3f?-1:need[n]);
	return 0;
}

WA,2,5,6点