#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=210;
unordered_map<int,int> mp;
typedef pair<int,int> PII;
int n;
int m,t,s,e;
int a[N][N];
int f[N][N];
void mul(int a[][N],int b[][N])
{
int c[N][N];
memset(c,0x3f,sizeof c);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
memcpy(a,c,sizeof c);
}
int work(int m)
{
for(int i=1;i<=n;i++)
a[i][i]=0;
while(m)
{
if(m&1)mul(a,f);
mul(f,f);
m>>=1;
}
return a[s][e];
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>m>>t>>s>>e;
if(!mp.count(s))mp[s]=++n;
if(!mp.count(e))mp[e]=++n;
s=mp[s],e=mp[e];
memset(a,0x3f,sizeof a);
memset(f,0x3f,sizeof f);
for(int i=1;i<=t;i++)
{
int a,b,w;
cin>>w>>a>>b;
if(!mp.count(a))mp[a]=++n;
if(!mp.count(b))mp[b]=++n;
a=mp[a],b=mp[b];
f[a][b]=min(f[a][b],w);
f[b][a]=min(f[b][a],w);
}
cout<<work(m)<<endl;
return 0;
}