RT,WA on #2,#3,#10,#11

#include <iostream>
#include <queue>
#define int long long
using namespace std;

int n, m, k, tot = 0;
int head[8000005], ver[8000005], to[8000005], edge[8000005];
int dis[8000050];
bool vis[8000050];
priority_queue< pair<int, int> > q;

void dij(){
	for(int i = 1;i <= 200049;i ++)dis[i] = 0x3f3f3f3f;
	dis[1] = 0;
	q.push(make_pair(0, 1));
	while(!q.empty()){
		int x = q.top().second;
		q.pop();
		if(vis[x])continue;
		vis[x] = 1;
		for(int i = head[x];i;i = to[i]){
			int y = ver[i];
			int val = edge[i];
			if(dis[y] > dis[x] + val){
				dis[y] = dis[x] + val;
				q.push(make_pair(-dis[y], y));
			}
		}
	}
}

void add(int x, int y, int z){
	ver[++ tot] = y;
	edge[tot] = z;
	to[tot] = head[x];
	head[x] = tot;
}

signed main(){
	ios::sync_with_stdio(0);
	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;
		for(int j = 0;j <= k;j ++){
			add(u + j * n, v + j * n, w);
			add(v + j * n, u + j * n, w);
			if(j == k)break;
			add(u + j * n, v + (j+1) * n, 0);
			add(v + j * n, u + (j+1) * n, 0);
		}
	}
	dij();
	int ans = 0x3f3f3f3f3f3f;
	for(int i = 1;i <= k;i ++){
		ans = min(ans, dis[n + i * n]);
	}
	cout << ans << endl;
	return 0;
}