#include <bits/stdc++.h>
using namespace std;
int n,t,s,e;
int num[100100],tot;
struct Drind{
	int a[505][505];
}dis,ans;
Drind operator * (const Drind x,const Drind y){
	Drind c;
	memset(c.a,0x3f,sizeof(c.a));
	for (int k=1;k<=n;k++)			
	    for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				c.a[i][j] = min(c.a[i][j],x.a[i][k] + y.a[k][j]);
	return c;
}
int main()
{
    cin >> n >> t >> s >> e;
    for (int i=1,u,v,w;i<=t;i++){
    	cin >>u >> v >> w;
    	if (!num[u])
    	    num[u] = ++tot;
    	if (!num[v])
    	    num[v] = ++tot;
    	dis.a[num[u]][num[v]] = dis.a[num[v]][num[u]] = w;
	}
	n--;
	ans = dis;
	for (;n;n>>=1,dis = dis * dis){
		if (n & 1)
		    ans = ans * dis;
	}
	cout << ans.a[num[s]][num[e]] << endl;
	return 0;
}