#include<stdio.h>
#include<iostream>
using namespace std;
int n,m,s,e,w[1005],ra[105],rb[105],l[105],N;
struct wzf
{long long t[105][105];
}a,first,ans;
long long Min(long long a,long long b){return a<b?a:b;}
wzf times(wzf a,wzf b)
{int i,j,k;
 wzf c;
 for(i=1;i<=N;i++)
  for(j=1;j<=N;j++)
  {c.t[i][j]=214748363700000ll;
   for(k=1;k<=N;k++) c.t[i][j]=Min(c.t[i][j],a.t[i][k]+b.t[k][j]);
  }
 return c;
}
wzf quick(int k)
{wzf sum=first,s=a;
 int i=1;
 while(k)
 {if(k&1)
  {if(i!=1) sum=times(sum,s);
   else sum=s;
   i++;
  }
  s=times(s,s);
  k>>=1;
 }
 return sum;
}
int main()
{cin>>n>>m>>s>>e;
 int i,j;
 for(i=1;i<=m;i++) cin>>l[i]>>ra[i]>>rb[i];
 for(i=1;i<=m;i++)
 {if(w[ra[i]]==0) w[ra[i]]=++N;
  if(w[rb[i]]==0) w[rb[i]]=++N;
 }
 for(i=1;i<=N;i++)
  for(j=1;j<=N;j++)
   a.t[i][j]=1000000000000000ll;
 for(i=1;i<=m;i++) a.t[w[ra[i]]][w[rb[i]]]=a.t[w[rb[i]]][w[ra[i]]]=l[i];
 ans=quick(n);
 cout<<ans.t[w[s]][w[e]];
 return 0;
}