spfa

#include<bits/stdc++.h>
using namespace std;
int cnt=1,n,m,k,s,t,head[100005],dis[100005];
bool vi[100005];
struct edge{
int v,w,next;
}e[2500005];
void add(int u,int v, int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}

int main(){
memset(dis,0x3f,sizeof(dis));
memset(vi,0,sizeof(vi));
scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
s++,t++;
int a,b,c;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&a,&b,&c);
a++,b++;
add(a,b,c);add(b,a,c);
for(int j=1;j<=k;j++){
add(a+j*n,b+j*n,c);
add(b+j*n,a+j*n,c);
add(a+(j-1)*n,b+j*n,0);
add(b+(j-1)*n,a+j*n,0);
}} 
for(int j=1;j<=k;j++) add(t+(j-1)*n,t+j*n,0); 
dis[s]=0;
queue<int> q;
q.push(s);
while(!q.empty()){
int x=q.front();
q.pop();
vi[x]=0;
for(int i=head[x];i;i=e[i].next){
if(dis[e[i].v]>dis[x]+e[i].w){
dis[e[i].v]=dis[x]+e[i].w;
if(!vi[e[i].v]){ q.push(e[i].v);vi[e[i].v]=1;}
}}}

printf("%d",dis[t+n*k]);
return 0;


}