#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
long long n, m, k, u, v, w, dis[250005], flag[250005], ans = 1e18;
vector<pii> g[250005];
priority_queue<pii, vector<pii>, greater<pii> > q;
signed main(){
    cin>>n>>m>>k;
    for(int i = 1;i <= m;i++){
        cin>>u>>v>>w;
        for(int j = 0;j <= k;j++){
			int x = j * n + u;
			int y = j * n + v;
            g[x].push_back(make_pair(y, w));
			g[y].push_back(make_pair(x, w));
		}      
		for(int j = 0;j < k;j++){
			int x = j * n + u;
			int y = (j + 1) * n + v;
            g[x].push_back(make_pair(y, w / 2));
			x = j * n + v;
			y = (j + 1) * n + u;
			g[x].push_back(make_pair(y, w / 2));
		}
    }
    for(int i = 1;i <= (k + 1) * n;i++)
        dis[i] = 1e18;
    dis[1] = 0;
    q.push(make_pair(0, 1));
    while(!q.empty()){
        int k = q.top().second;
        q.pop();
        if(!flag[k]){
            flag[k] = 1;
            for(int i = 0;i < g[k].size();i++){
                v = g[k][i].first;
                w = g[k][i].second;
                if(dis[v] > dis[k] + w){
                    dis[v] = dis[k] + w;
                    q.push(make_pair(dis[v], v));
                }
            }
        }
    }
	for(int i = 1;i <= k;i++)
		ans = min(ans, dis[k * n + n]);
	cout<<ans;
    return 0;
}