#include <bits/stdc++.h>
#define pii pair <int , int>
using namespace std;
const int maxn = 210005;
int n , m , k;
vector <pii> G[maxn];
int dis[maxn] , vis[maxn];
priority_queue <pii , vector <pii> , greater<pii> > Q;
void add(int u , int v , int w) {
	G[u].push_back({v , w});
	G[v].push_back({u , w});
	for(int i = 1 ; i <= k ; ++ i) {
		G[u + (k - 1) * n].push_back({v + k * n , 0});
		G[v + k * n].push_back({u + (k - 1) * n , 0});
		G[u + k * n].push_back({v + k * n , w});
		G[v + k * n].push_back({u + k * n , w});
	}
}
void dijkstra(int st) {
	memset(dis , 0x3f3f3f , sizeof dis);
	dis[st] = 0;
	Q.push({dis[st] , st});
	while(!Q.empty()) {
		pii t = Q.top();
		Q.pop();
		if(vis[t.second]) continue;
		vis[t.second] = 1;
		for(int i = 0 ; i < G[t.second].size() ; ++ i) {
			int v = G[t.second][i].first;
			int c = G[t.second][i].second;
			if(!vis[v] && dis[v] > dis[t.second] + c) {
				dis[v] = dis[t.second] + c;
				Q.push({dis[v] , v});
			}
		}
	}
}
int main()
{
	//freopen(".in" , "r" , stdin);
	//freopen(".out" , "w" , stdout);
	cin >> n >> m >> k;
	for(int i = 1 ; i <= m ; ++ i) {
		int x , y , z;
		cin >> x >> y >> z;
		add(x , y , z);
	}
	dijkstra(1);
	cout << dis[n * (k + 1)] << endl;
	return 0;
}

本蒟蒻将对帮助到我的dalao赠送1~3个永久关注！