#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;
int n,m,k,s,t;
int dis[N][N];
bool vis[N][N];
struct node
{
	int id,w,cnt;
	bool operator < (const node & tmp) const
	{
		return w>tmp.w;
	}
};
vector<node> e[N];
priority_queue<node> pq;
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof(vis));
	dis[s][0]=0;
	pq.push({s,dis[s][0],0});
	while(!pq.empty())
	{
		node t=pq.top();
		pq.pop();
		int x=t.id,l=t.cnt;
		if(vis[x][l]==1)continue;
		vis[x][l]=1;
		for(int i=0;i<e[x].size();i++)
		{
			int y=e[x][i].id;
			int w=e[x][i].w;
			if(dis[x][l]+w<dis[y][l])
			{
				dis[y][l]=dis[x][l]+w;
				pq.push({y,dis[y][l],l});
			}
			if(l<k&&dis[x][l]+w/2<dis[y][l+1])
			{
				dis[y][l+1]=dis[x][l]+w/2;
				pq.push({y,dis[y][l+1],l+1});
			}
		}
	}
	return ;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		e[u].push_back({v,w});
		e[v].push_back({u,w});		
	}
	dijkstra(1);
	int ans=1e18;
	for(int i=0;i<=k;i++)ans=min(ans,dis[n][i]);
	cout<<ans;
	return 0;
} 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int dis[N][N],n,m;
void floyd()
{
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
}
void check()
{
	int sum=0x3f3f3f3f3f3f3f3f;
	for(int u=1;u<n;u++)
	{
		for(int w=u+1;w<=n;w++)
		{
			int ans=0;
			for(int i=1;i<n;i++)
			{
				for(int j=i+1;j<=n;j++)
				{
					ans+=min(min(dis[i][u]+dis[w][j],dis[i][w]+dis[u][j]),dis[i][j]);
				}
			}
			sum=min(sum,ans);
		}
	}
	cout<<sum;
	return ;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=n;i++)dis[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int x,y,w;
		cin>>x>>y>>w;
		dis[x][y]=w;
		dis[y][x]=w;
	}
	floyd();
	check();
	return 0;
}