link，又WA又T的

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#define re register
using namespace std;

const int N = 1e7;

int n,m,k,s,t,cnt;
int head[N],dis[N];
bool vis[N];

struct edge{
	int v,w,next;
}e[N];

inline void add(int u,int v,int w){
	cnt ++;
	e[cnt].v = v;
	e[cnt].w = w;
	e[cnt].next = head[u];
	head[u] = cnt;
}

inline void cs(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(head,-1,sizeof(head));
	memset(dis,0x3f,sizeof(dis));
}

inline void SPFA(){
	queue<int> q;
	q.push(s);
	vis[s] = true;
	dis[s] = 0;
	while(! q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = false;
		for(re int i = head[u];i != -1;i = e[i].next){
			re int v = e[i].v;
			if(dis[v] > dis[u] + e[i].w){
				dis[v] = dis[u] + e[i].w;
				if(! vis[v]){
					q.push(v);
					vis[v] = true;
				}
			}
		}
	}
}

int main(){
	cs();
	cin>>n>>m>>k;
	cin>>s>>t;
	s ++;
	t ++;
	for(re int i = 1;i <= m;i ++){
		int a,b,c;
		cin>>a>>b>>c;
		a ++;
		b ++;
		add(a,b,c);
		add(b,a,c);
		for(re int j = 0;j <= k;j ++){
			add(a + (j - 1) * n,b + j * n,0);
			add(b + (j - 1) * n,a + j * n,0);
			add(a + j * n,b + j * n,c);
			add(b + j * n,a + j * n,c);
		}
	}
	SPFA();
	cout<<dis[t + k * n]<<"\n";
	return 0;
}