#include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cstdlib>

 #define ll long long

 #define ull unsigned long long

 #define d double

 using namespace std;

 const int maxn=,inf=;

 struct mat{int f[][];}f,c;

 int id[];

 int i,j,k,n,m,cnt,st,ed;

 int ra,fh;char rx;

 inline int read(){

     rx=getchar(),ra=,fh=;

     while((rx<''||rx>'')&&rx!='-')rx=getchar();

     if(rx=='-')fh=-,rx=getchar();

     while(rx>=''&&rx<='')ra*=,ra+=rx-,rx=getchar();return ra*fh;

 }

 inline int min(int a,int b){return a<b?a:b;}

 inline mat run(mat &a,mat &b){

     register int i,j,k;

     for(i=;i<=cnt;i++)for(j=;j<=cnt;j++)

         for(c.f[i][j]=inf,k=;k<=cnt;k++)

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

     return c;

 }

 int main(){

     n=read(),m=read(),st=read(),ed=read();int x;

     memset(f.f,,sizeof(f.f));

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

         x=read(),j=read(),k=read();

         if(!id[j])id[j]=++cnt;if(!id[k])id[k]=++cnt;

         j=id[j],k=id[k];

         f.f[j][k]=min(f.f[j][k],x),f.f[k][j]=min(f.f[k][j],x);

     }

     mat g=f;n--;

     while(n){

         if(n&)g=run(g,f);

         n>>=;

         if(n)f=run(f,f);

     }

     printf("%d\n",g.f[id[st]][id[ed]]);

 }