rt，样例输出 $0$。

#include<cstdio>
#include<queue>
using namespace std;
const int MAXN=110005,MAXM=22000005,INF=0x3f3f3f3f;
int cnt=0,head[MAXN],d[MAXN];
bool vis[MAXN];
struct Edge {
  int end,val,next;
}edge[MAXM];
struct Node {
  int num,dis;
  bool operator <(const Node &x) const {
  	return dis>x.dis;
  }
};
void add(int u,int v,int w) {
  edge[++cnt].next=head[u];
  edge[cnt].end=v;
  edge[cnt].val=w;
  head[u]=cnt;
}
void Dijkstra(int n,int s) {
  for(int i=0;i<=n;i++)
    d[i]=INF;
  d[s]=0;
  priority_queue<Node>q;
  q.push((Node){s,0});
  while(!q.empty()) {
  	Node p=q.top();
  	q.pop();
  	if(vis[p.num])
  	  continue;
  	vis[p.num]=true;
  	for(int i=head[p.num];i!=0;i=edge[i].next) {
  	  if(!vis[edge[i].end]&&d[p.num]+edge[i].val<d[edge[i].end]) {
  	  	d[edge[i].end]=d[p.num]+edge[i].val;
  	  	if(!vis[edge[i].end])
  	  	  q.push((Node){edge[i].end,d[edge[i].end]});
  	  }
  	}
  }
}
int main() {
  int n,m,k,s,t,u,v,w;
  scanf("%d %d %d %d %d",&n,&m,&k,&s,&t);
  s++;
  t++;
  for(int i=1;i<=m;i++) {
  	scanf("%d %d %d",&u,&v,&w);
  	u++;
  	v++;
  	add(u,v,w);
  	add(v,u,w);
  	for(int j=1;j<=k;j++) {
  	  add(u+j*n,v+j*n,w);
  	  add(v+j*n,u+j*n,w);
  	  add(u+j*n-n,v+j*n,0);
  	  add(v+j*n-n,u+j*n,0);
  	}
  }
  Dijkstra(n,s);
  int ans=INF;
  for(int i=0;i<=k;i++)
    if(d[t+i*n]<ans)
      ans=d[t+i*n];
  printf("%d",ans);
  return 0;
}