#include <iostream>

 #include <algorithm>

 #include <queue>

 #include <stdio.h>

 using namespace std;

 int m,n,s,t,k;

 #define M 100005

 #define N 1005

 #define INF 100000000

 int dis[N];

 struct edge

 {

     int v,val,next;//边的终点，边权

     edge(){}

     edge(int _v,int _val,int _next){v=_v,val=_val,next=_next;}

 }line[M],_line[M];

 int head[M],_head[M];

 struct dijnode

 {

     int v,dis;

     dijnode(){}

     dijnode(int _v,int _dis){v=_v,dis=_dis;}

     friend bool operator <(const dijnode &a,const dijnode &b)

     {

         return a.dis>b.dis;

     }

 };

 struct Anode

 {

     int v,g,h;//v:当前点 g:起点到点v距离 h:点v到终点距离

     Anode(){}

     Anode(int _v,int _g,int _h){v=_v,g=_g;h=_h;}

     friend bool operator <(const Anode&a,const Anode&b)

     {

         return a.h+a.g>b.h+b.g;

     }

 };

 void input(){

     memset(head,-,sizeof(head));

     memset(_head,-,sizeof(_head));

     int u,v,val;

     int e=,_e=;

     for(int i=;i<m;i++)

     {

         scanf("%d%d%d",&u,&v,&val);

         line[e]=edge(v,val,head[u]);

         head[u]=e++;

         _line[_e]=edge(u,val,head[v]);

         _head[v]=_e++;

     }

 }

 int vis[N];

 void dijkstra()

 {

     memset(vis,,sizeof(vis));

     priority_queue<dijnode>pq;

     for(int i=;i<n;i++)

         dis[i]=INF;

     dijnode node =dijnode(t,);

     dis[t]=;

     pq.push(node);

     while(!pq.empty())

     {

         dijnode tmp = pq.top();

         pq.pop();

         if(vis[tmp.v])continue;

         vis[tmp.v]=;

         for(int i=_head[tmp.v];i!=-;i=_line[i].next)

         {

             if(tmp.dis+_line[i].val<dis[_line[i].v])

             {

                 dis[_line[i].v]=tmp.dis+_line[i].val;

                 pq.push(dijnode(_line[i].v,dis[_line[i].v]));

             }

         }

     }

     for(int i=;i<=n;i++)printf("%d\n",dis[i]);

 }

 int kcnt[N];

 int Astar()

 {

     if(dis[s]>=INF)return -;

     memset(kcnt,,sizeof(kcnt));

     priority_queue<Anode> pq;

     pq.push(Anode(s,,dis[s]));

     Anode node;

     while(!pq.empty())

     {

         node = pq.top();

         pq.pop();

         if(kcnt[node.v]>=k)continue;

         kcnt[node.v]++;

         if(kcnt[t]>=k)return node.g;

         for(int i=head[node.v];i!=-;i = line[i].next)

         {

             pq.push(Anode(line[i].v,node.g+line[i].val,dis[line[i].v]));

         }

     }

     return -;

 }

 int main(int argc, const char * argv[])

 {

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         input();

         scanf("%d%d%d",&s,&t,&k);

         dijkstra();

         printf("%d\n",Astar());

     }

 }