#include<queue>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 5e6 + 10;
int n,m,k,u,v,w;
int h[N],ver[N],e[N],ne[N],idx;
bool st[N];
long long d[N];
void add(int u,int v,int w){
	idx++,ver[idx] = v,e[idx] = w,ne[idx] = h[u],h[u] = idx;
}
void dij(){
    priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> heap;
    heap.push({0,1});
    memset(d,0x3f,sizeof(d));
    d[1] = 0;
    while(heap.size()){
        pair <int,int> T = heap.top();
        heap.pop();
        int x = T.second;
        if(st[x]){
            continue;
        }
        st[x] = true;
        for(int i = h[x];i;i = ne[i]){
            int j = ver[i];
            if(d[x] + e[i] < d[j]){
                d[j] = d[x] + e[i];
                heap.push({d[j],j});
            }
        }
    }
}
int main(){
	cin >> n >> m >> k;
	for(int j = 1;j <= m;j++){
		cin >> u >> v >> w;
		add(u,v,w),add(v,u,w);
		for(int i = 1;i <= k;i++){
			add(u + n * i,v + n * i,w);
			add(v + n * i,u + n * i,w);
			add(u + n * (i - 1),v + n * i,0);
			add(v + n * (i - 1),u + n * i,1);
		}
	}
	dij();
	long long ans = d[n];
	for(int i = 1;i <= k;i++){
	    ans = min(ans,d[n * (i + 1)]);
	}
	cout << ans;
	return 0;
}