#include<bits/stdc++.h>
using namespace std;
const int N=60,inf=0x3f3f3f3f;
int n,k,m,tu[N][N],dist[N][N][N];
signed main(){
	cin>>n>>m>>k;
	memset(dist,inf,sizeof(dist));
	memset(tu,inf,sizeof(tu));
	for(int i=1;i<=m;i++){
		int aa,bb,tt;
		cin>>aa>>bb>>tt;
		tu[aa][bb] = tu[bb][aa] = tt;
		dist[aa][bb][0] = dist[bb][aa][0] = tt;
	}
	for(int d=1;d<=n;d++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(i==j || j==d || i==d) continue;
				dist[i][j][0] = min(dist[i][j][0],dist[i][d][0] + dist[d][j][0]);
			}
		}
	}
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++){
			dist[i][j][1] = dist[i][j][0];
			if(tu[i][j] != inf) dist[i][j][1] = tu[i][j]/2;
		} 
	
	for(int t=1;t<=k;t++){
		for(int d=1;d<=n;d++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(i==j || i==d || j==d) continue;
					dist[i][j][t] = min(dist[i][j][t],dist[i][d][t-1] + tu[d][j]/2);
				}
			}
		}
		
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++) dist[i][j][t+1] = dist[i][j][t];
	}
	
	cout<<min(dist[1][n][k],dist[n][1][k])<<"\n";
	return 0;
}