[cpp]
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1001;
const int maxm=100001;
const int inf=1<<30;
struct edge
{
int from,to,next,w;
};
edge e1[maxm];
edge e2[maxm];
int head1[maxn];
int head2[maxn];
int dist[maxn];
bool vis[maxn];
struct node//存儲搜索過程中點的信息
{
int to;
int g,f;//f=g+h
bool operator <(const node &r) const
{
if(r.f==f) return r.g<g;
else return r.f<f;
}
};
int n,m,t1,t2,k,cnt,s,end;//第k短路
void add1(int i,int j,int w)
{
e1[t1].from=i;
e1[t1].to=j;
e1[t1].w=w;
e1[t1].next=head1[i];
head1[i]=t1++;
}
void add2(int i,int j,int w)
{
e2[t2].from=i;
e2[t2].to=j;
e2[t2].w=w;
e2[t2].next=head2[i];
head2[i]=t2++;
}
void spfa(int s)//求出路徑當前值到終點的最短距離
{
queue <int> q;
q.push(s);
for(int i=1;i<=n;i++) dist[i]=inf;
memset(vis,false,sizeof(vis));
dist[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=false;//用vis來標記點是否在隊列中
for(int i=head2[u];i!=-1;i=e2[i].next)
{
int v=e2[i].to;
if(dist[v]>dist[u]+e2[i].w)
{
dist[v]=dist[u]+e2[i].w;
if(!vis[v])
{
q.push(v);
vis[v]=true;
}
}
}
}
}
int A(int s,int end,int k)
{
int cnt=0;
node e,ne;
priority_queue <node> que;
if(s==end) k++;//特判
if(dist[s]==inf) return -1;
e.to=s;
e.f=e.g+dist[e.to];//估價函數的公式
que.push(e);
while(!que.empty())
{
e=que.top();
que.pop();
if(e.to==end) cnt++;//統計終點出隊的次數
if(cnt==k) return e.g;//計算t出隊的次數，如果t出對的次數=k，則當前的路徑長度g記為第k短路
for(int i=head1[e.to];i!=-1;i=e1[i].next)
{
ne.to=e1[i].to;
ne.g=e.g+e1[i].w;
ne.f=ne.g+dist[ne.to];
que.push(ne);
}
}
return -1;
}
int main()
{
int u,v,w;
while(scanf("%d%d",&n,&m)==2)
{
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head2));
memset(e1,0,sizeof(e1));
memset(e2,0,sizeof(e2));
t1=t2=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
add1(u,v,w);
add2(v,u,w);
}
scanf("%d%d%d",&s,&end,&k);
spfa(end);
int ans=A(s,end,k);
printf("%d\n",ans);
}
return 0;
}
