#include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 #define INF (1<<29)

 int N;

 struct Mat{

     int m[][];

     Mat(){

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

             for(int j=; j<; ++j) m[i][j]=INF;

         }

     }

 };

 Mat operator*(const Mat &m1,const Mat &m2){

     Mat m;

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

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

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

                 m.m[i][j]=min(m.m[i][j],m1.m[i][k]+m2.m[k][j]);

             }

         }

     }

     return m;

 };

 int idx[];

 int main(){

     Mat m;

     int n,t,s,e,a,b,c;

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

     memset(idx,-,sizeof(idx));

     while(t--){

         scanf("%d%d%d",&c,&a,&b);

         if(idx[a]==-){

             idx[a]=N++;

         }

         if(idx[b]==-){

             idx[b]=N++;

         }

         m.m[idx[a]][idx[b]]=m.m[idx[b]][idx[a]]=c;

     }

     --n;

     Mat ans=m;

     while(n){

         if(n&){

             ans=ans*m;

         }

         m=m*m;

         n>>=;

     }

     printf("%d",ans.m[idx[s]][idx[e]]);

     return ;

 }