#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000005
struct node
{
	int u1,v1;
};
struct n
{
	int u1,v1;
	friend bool operator <(n a,n b)
	{
		return a.v1>b.v1;
	}
}tmp;
vector<node>p[MAXN];
priority_queue<n>q;
int n,m,s,k,t;
int dis[MAXN],vis[MAXN];
void dijkstra()
{
	for(int i=0;i<=n+k*n;i++)
	{
		dis[i]=INT_MAX;
	}
	dis[s]=0;
	tmp.u1=s,tmp.v1=0;
	q.push(tmp);
	while(!q.empty())
	{
		int u=q.top().u1;
		q.pop();
		if(vis[u])
			continue;
		vis[u]=1;
		for(int i=0;i<p[u].size();i++)
		{
			if(dis[p[u][i].u1]>(long long)dis[u]+p[u][i].v1)
			{
				dis[p[u][i].u1]=dis[u]+p[u][i].v1;
				tmp.u1=p[u][i].u1,tmp.v1=dis[p[u][i].u1];
				q.push(tmp);
			}
		}
	}
}
int main()
{
 	cin>>n>>m>>k;
 	s=1,k=n;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		p[x].push_back(node{y,z});
		p[y].push_back(node{x,z});
		for(int j=1;j<=k;j++)
		{
			p[x+j*n].push_back(node{y+j*n,z});
			p[y+j*n].push_back(node{x+j*n,z});
			p[x+j*n-n].push_back(node{y+j*n,z/2});
			p[y+j*n-n].push_back(node{x+j*n,z/2});
		}
	}
	dijkstra();
	int ans=INT_MAX;
	for(int i=0;i<=k;i++)
	{
		if(dis[t+i*n]<ans)
			ans=dis[t+i*n];
	}
	cout<<ans;
}