#include<iostream>
#include<algorithm>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<vector>
#include<deque>
#define ll long long
#define ull unsigned long long
using namespace std;
int n,m,k;
struct str
{
	vector <pair<int,int>> edge;
	int cnt;
}mp[60];
void add_edge(int x,int y,int weight)
{
	mp[x].cnt++;
	mp[x].edge.push_back(make_pair(y,weight));
}
int dis[60][1010];
void bfs()
{
	deque <pair<int,int>> dq;
	dq.push_back(make_pair(1,0));
	dis[1][0]=0;
	while(!dq.empty())
	{
		int now_node=dq.front().first;
		int num=dq.front().second;
		dq.pop_front();
		int cnt=mp[now_node].cnt;
		for(int i=0;i<cnt;i++)
		{
			int next_node=mp[now_node].edge[i].first;
			int weight=mp[now_node].edge[i].second;
			if(num<k)
			{
				if(dis[next_node][num+1]==-1)
				{
					dis[next_node][num+1]=dis[now_node][num]+(weight>>1);
					dq.push_front(make_pair(next_node,num+1));
				}
				else
				{
					if(dis[now_node][num]+(weight>>1)<dis[next_node][num+1])
					{
						dis[next_node][num+1]=dis[now_node][num]+(weight>>1);
						dq.push_front(make_pair(next_node,num+1));
					}
				}
			}
			if(dis[next_node][num]==-1)
			{
				dis[next_node][num]=dis[now_node][num]+weight;
				dq.push_back(make_pair(next_node,num));
			}
			else
			{
				if(dis[now_node][num]+weight<dis[next_node][num])
				{
					dis[next_node][num]=dis[now_node][num]+weight;
					dq.push_back(make_pair(next_node,num));
				}
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	memset(dis,-1,sizeof(dis));
	std::cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int a,b,t;
		std::cin>>a>>b>>t;
		add_edge(a,b,t);
		add_edge(b,a,t);
	}
	bfs();
	int ans=1e9;
	for(int i=0;i<=k;i++)
	{
		if(dis[n][i]!=-1)
		{
			ans=min(dis[n][i],ans);
		}
	}
	std::cout<<ans;
	return 0;
}

rt，感觉有点奇怪