/*poj 2449 k短路 A* 估价函数是 s到i的距离+i到t的距离 */#include<cstdio>#include<queue>#include<vector>#define inf 1e7#define maxn 100010using namespace std;int n,m,S,T,K,num1,num2,head1[maxn],head2[maxn],dis[maxn];int q[maxn],hea,tai,f[maxn],cnt,ans;struct edge{    int v,t,pre;}e1[maxn],e2[maxn];struct node{    int v,f,g;    bool operator < (const node &x)const{        return (f==x.f&&g>x.g)||f>x.f;//注意重载的时候>     } };priority_queue<node>Q;int init(){    int x=0,f=1;char s=getchar();    while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();}    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x*f;}void Add1(int from,int to,int dis){    num1++;e1[num1].v=to;    e1[num1].t=dis;    e1[num1].pre=head1[from];    head1[from]=num1;}void Add2(int from,int to,int dis){    num2++;e2[num2].v=to;    e2[num1].t=dis;    e2[num1].pre=head2[from];    head2[from]=num2;}void Cl(){    num1=num2=ans=cnt=0;    for(int i=1;i<=n;i++)        head1[i]=head2[i]=f[i]=0;}void SPFA1(){    for(int i=1;i<=n;i++)dis[i]=inf;    f[T]=1;dis[T]=0;hea=0;tai=0;    q[++tai]=T;    while(hea<=tai){        int k=q[++hea];f[k]=0;        for(int i=head2[k];i;i=e2[i].pre){            int v=e2[i].v;            if(dis[v]>dis[k]+e2[i].t){                dis[v]=dis[k]+e2[i].t;                if(f[v]==0){                    f[v]=1;q[++tai]=v;                }            }        }    }}void SPFA2(){    while(!Q.empty())Q.pop();    Q.push((node){S,dis[S],0});    if(S==T)K++;//题目要求 0 不能算一条路....     if(dis[S]>=inf){        ans=-1;return;    }    while(!Q.empty()){        node x=Q.top();Q.pop();        int u=x.v;        if(u==T)cnt++;        if(cnt==K){            ans=x.g;return;        }        for(int i=head1[u];i;i=e1[i].pre){            node y;y.v=e1[i].v;            y.g=x.g+e1[i].t;            y.f=y.g+dis[e1[i].v];            Q.push(y);        }    }    ans=-1;}int main(){    while(~scanf("%d%d",&n,&m)){        Cl();int u,v,t;        for(int i=1;i<=m;i++){            u=init();v=init();t=init();            Add1(u,v,t);Add2(v,u,t);        }        S=init();T=init();K=init();        SPFA1();SPFA2();printf("%d\n",ans);    }    return 0;}