#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
#define maxN 210
#define INF 0xfffffff
#define MIN(a, b) ((a)<(b)?(a):(b))
map<int, int> match;
int g[maxN][maxN], ans[maxN][maxN];
int city;
void clean(int dest[][maxN], int a){
	for(int i=0; i<city; i++)
	for(int j=0; j<city; j++)
	dest[i][j]=a;
}
void multi(int dest[][maxN], int src1[][maxN], int src2[][maxN]){
	for(int k=0; k<city; k++)
	for(int i=0; i<city; i++)
	for(int j=0; j<city; j++)
	dest[i][j]=MIN(dest[i][j], src1[i][k]+src2[k][j]);
}
void copy(int dest[][maxN], int src[][maxN]){
	for(int i=0; i<city; i++)
	for(int j=0; j<city; j++)
	dest[i][j]=src[i][j];
}
void out(int dest[][maxN]){
	for(int i=0; i<city; i++){
		for(int j=0; j<city; j++)
		printf("%d ", dest[i][j]);
		cout<<endl;
	}
	cout<<endl;
}
void set(int dest[][maxN]){
	for(int i=0; i<city; i++)
	for(int j=0; j<city; j++){
		if(i==j) dest[i][j]=0;
		else dest[i][j]=INF;
	}
}
void calc(int exp){
	int fac[maxN][maxN], temp[maxN][maxN];
	copy(fac, g);
	set(ans);
	while(exp){
		if(exp & 0x1){
			clean(temp, INF);
			multi(temp, ans, fac);
			copy(ans, temp);
//			out(ans);
		}
		clean(temp, INF);
		multi(temp, fac, fac);
		copy(fac, temp);
		exp>>=1;
	}
}
int main(){
	int n, t, s, e, a, b, l, fa, fb;
	scanf("%d %d %d %d", &n, &t, &s, &e);
	for(int i=0; i<maxN; i++)
	for(int j=0; j<maxN; j++)
	g[i][j]=INF;
	city=0;
	for(int i=0; i<t; i++){
		scanf("%d %d %d", &l, &a, &b);
		if(match.find(a)==match.end()) match[a]=city++;
		if(match.find(b)==match.end()) match[b]=city++;
		fa=match[a]; fb=match[b];
		g[fa][fb]=l; g[fb][fa]=l;
	}
	calc(n);
	cout<<ans[match[s]][match[e]]<<endl;
	return 0;
}