#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#include <iostream>

#include <cstdlib>

#include <queue>

using namespace std;

#define N 10005

struct node

{

	int to,next,val;

}e[N*10];

int head[N],cnt,dis[N],vis[N],n,m,k;

priority_queue < pair<int ,int > >q;

void add(int x,int y,int z)

{

	e[cnt].to=y;

	e[cnt].next=head[x];

	e[cnt].val=z;

	head[x]=cnt++;

}

void Dijkstra()

{

	memset(vis,0,sizeof(vis));

	while(!q.empty())q.pop();int num=0;

	for(int i=1;i<=n;i++)q.push(make_pair(-dis[i],i));

	while(!q.empty())

	{

		int x=q.top().second;q.pop();

		if(vis[x])continue;

		vis[x]=1;num++;

		if(num==n)break;

		for(int i=head[x];i!=-1;i=e[i].next)

		{

			int to1=e[i].to;

			if(dis[to1]>dis[x]+e[i].val)

			{

				dis[to1]=dis[x]+e[i].val;

				q.push(make_pair(-dis[to1],to1));

			}

		}

	}

}

int g[N];

int main()

{

	memset(head,-1,sizeof(head));

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1;i<=m;i++)

	{

		int x,y,z;scanf("%d%d%d",&x,&y,&z);

		add(x,y,z);add(y,x,z);

	}

	memset(dis,0x3f,sizeof(dis));dis[1]=0;

	for(int i=0;i<=k;i++)

	{

		Dijkstra();

		if(i!=k)

		{

			for(int x=1;x<=n;x++)g[x]=dis[x];

			for(int x=1;x<=n;x++)

			{

				for(int j=head[x];j!=-1;j=e[j].next)

				{

					g[e[j].to]=min(dis[x],g[e[j].to]);

				}

			}

			for(int x=1;x<=n;x++)dis[x]=g[x];

		}

	}

	printf("%d\n",dis[n]);

}