#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int n,m,k,s,t;
struct Edge{
	int to;
	int d;
	int nxt;
}e[10*N];
int cnt,head[N];
int f[N][31];
void add_edge(int x,int y,int z)
{
	e[++cnt].nxt=head[x];
	e[cnt].to=y;
	e[cnt].d=z;
	head[x]=cnt; 
}

void SPFA()
{
	for(int i=0;i<=k;i++)
	{
		queue<pair<int,int> > q;
		q.push(make_pair(s,0));
		while(!q.empty())
		{
			pair<int,int> h;
			h=q.front();
			q.pop();
			if(h.second>f[h.first][i]) continue;
			for(int j=head[h.first];j;j=e[j].nxt)
			{
				bool flag=0;
				if(i>1)
				{
					if(f[h.first][i-1]<f[e[j].to][i])
					{
						f[e[j].to][i]=f[h.first][i-1];
						flag=1;
					}
				}
				if(f[h.first][i]+e[j].d<f[e[j].to][i])
				{
					f[e[j].to][i]=f[h.first][i]+e[j].d;
					flag=1;
				}
				if(flag)
				{
					q.push(make_pair(e[j].to,f[e[j].to][i]));
				}
			} 
		} 
	} 
}
signed main()
{
	scanf("%d%d%d",&n,&m,&k);
	s=1;
	t=n;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add_edge(x,y,z);
		add_edge(y,x,z);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=k;j++) f[i][j]=1e9;
	}	
	for(int i=0;i<=k;i++) f[s][i]=0;
	SPFA();
	printf("%d\n",f[t][k]);
	return 0;
}