#include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int N=;

 int n,t,s,e,u[N],v[N],w[N],b[N],a[N],ma[],num,tot;

 struct jz{

     int a[N][N];

 }x;

 jz jzc(jz a,jz b){

     jz c;

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

         for(int j=;j<=num;j++){

             c.a[i][j]=;

         }

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

         for(int j=;j<=num;j++)

             for(int k=;k<=num;k++){

                 c.a[i][j]=min(c.a[i][j],a.a[i][k]+b.a[k][j]);

             }

     return c;

 }

 jz ksm(jz a,int k){

     jz ans=a;

     k--;

     while(k){

         if(k&){

             ans=jzc(ans,a);

         }

         k>>=;

         a=jzc(a,a);

     }

     return ans;

 }

 int main(){

     scanf("%d%d%d%d",&n,&t,&s,&e);

     for(int i=;i<=t;i++){

         scanf("%d%d%d",&w[i],&u[i],&v[i]);

         a[++tot]=u[i];

         b[tot]=u[i];

         a[++tot]=v[i];

         b[tot]=v[i];

     }

     sort(b+,b++tot);

     num=unique(b+,b++tot)-(b+);

     for(int i=;i<=tot;i++){

         ma[a[i]]=lower_bound(b+,b++num,a[i])-b;

     }

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

         for(int j=;j<=num;j++)

             x.a[i][j]=;

     for(int i=;i<=t;i++){

         x.a[ma[u[i]]][ma[v[i]]]=min(x.a[ma[u[i]]][ma[v[i]]],w[i]);

         x.a[ma[v[i]]][ma[u[i]]]=min(x.a[ma[v[i]]][ma[u[i]]],w[i]);

     }

     x=ksm(x,n);

     printf("%d",x.a[ma[s]][ma[e]]);

     return ;

 }

 /*

 2 6 6 4

 11 4 6

 4 4 8

 8 4 9

 6 6 8

 2 6 9

 3 8 9

 */