#include <bits/stdc++.h>
using namespace std ;
int n , t , s , e , w[505] , u[505] , v[505] , a[505] ;
struct mat
{
	int n , a[505][505] ;
	void mem()
	{
		memset(a , 0x3f , sizeof a) ;
		return ;
	}
	void putmat(int x)
	{
		n = x ;
		return ;
	}
	mat operator * (const mat &y) const
	{
		mat s ;
		s.mem() ;
		for(int i = 1 ; i <= n ; i++)
			for(int j = 1 ; j <= n ; j++)
				for(int k = 1 ; k <= n ; k++)
					s.a[i][j] = min(s.a[i][j] , a[i][k] + y.a[k][j]) ;
		return s ;
	}
} ;
mat base ;
mat fast_pow(int k)
{
	mat s = base ;
	k-- ;
	while(k)
	{
		if(k & 1)	s = s * base ;
		base = base * base , k >>= 1 ;
	}
	return s ;
}
int main()
{
	cin >> n >> t >> s >> e ;
	for(int i = 1 ; i <= t ; i++)
	{
		cin >> w[i] >> u[i] >> v[i] ;
		a[i * 2 - 1] = u[i] , a[i * 2] = v[i] ;
	}
	sort(a + 1 , a + 2 * t + 1) ;
	int sz = unique(a + 1 , a + 2 * t + 1) - a - 1 ;
	base.mem() ;
	base.putmat(sz) ;
	for(int i = 1 ; i <= t ; i++)
	{
		u[i] = lower_bound(a + 1 , a + sz + 1 , u[i]) - a , v[i] = lower_bound(a + 1 , a + sz + 1 , v[i]) - a ;
		base.a[u[i]][v[i]] = min(base.a[u[i]][v[i]] , w[i]) , base.a[v[i]][u[i]] = min(base.a[v[i]][u[i]] , w[i]) ;
	}
	base = fast_pow(n) ;
	s = lower_bound(a + 1 , a + sz + 1 , s) - a , e = lower_bound(a + 1 , a + sz + 1 , e) - a ;
	cout << base.a[s][e] ;
	return 0 ;
}