#include <bits/stdc++.h> 矩阵快速幂 + floyd
//#define int long long
using namespace std;
const int N = 210; //至多 2*T 个点
int id[1010],dist[N][N] , tmp[N][N];
int ans[N][N];
int n,m,s,e;
int k;
void floyd(int a[][N] , int b[][N] , int c[][N]){ //a用于存结果,b是第一个矩阵,c是第二个矩阵
memset(tmp , 0x3f , sizeof tmp);
for(int k = 1;k<=n;k++)
for(int i = 1;i<=n;i++)
for(int j = 1;j<=n;j++)
tmp[i][j] = min(tmp[i][j] , b[i][k] + c[k][j]);
memcpy(a,tmp,sizeof tmp);
}
void qmi(int k){
memset(ans, 0x3f , sizeof ans);
for(int i = 1;i<=n;i++) ans[i][i] = 0; // 计算自环 不等于0的话无法正常计算自环情况
while(k){
if(k&1) floyd(ans ,ans , dist);
floyd(dist , dist ,dist);
k >>= 1;
}
}
signed main()
{
ios::sync_with_stdio(0) ; cin.tie(0) ;
cin >> k >> m >> s >> e;
memset(dist,0x3f,sizeof dist);
for(int i = 0;i<m;i++){
int a,b,c;cin >> c >> a >> b;
if(!id[a]) id[a] = ++n;
if(!id[b]) id[b] = ++n;
int x = id[a] , y = id[b];
dist[y][x] = dist[x][y] = min(dist[x][y] , c);
}
qmi(k);
cout << ans[id[s]][id[e]] << endl;
return 0;
}