#include <bits/stdc++.h>
#define ll long long
#define R register int
#define mid (l+r>>1)
#define mod 45989
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
//#define int ll
char buf[1<<21],*p1=buf,*p2=buf;
using namespace std;
template<class T> void rd(T &k){
	char c=getchar();int f=1;k=0;
	while (c<'0' || c>'9'){if (c=='-') f*=-1;c=getchar();}
	while (c>='0' && c<='9') {k=k*10+c-'0';c=getchar();} 
	k*=f;
}
const int N=205;
int n,m,k,s,t,tot,b[N<<1],x,y,p;
struct node1{
	int len,s,t;
}a[N];
struct node{
	int a[N][N];
	node(){memset(a,0x3f,sizeof(a));}
	void operator*=(const node &kk){
		node res;
		for (int k=1;k<=tot;++k)
			for (int i=1;i<=tot;++i)
				for (int j=1;j<=tot;++j)
					res.a[i][j]=min(res.a[i][j],a[i][k]+kk.a[k][j]);
		for (int i=1;i<=tot;++i)
			for (int j=1;j<=tot;++j)
				a[i][j]=res.a[i][j];
	}
}A,B;
void qpow(int p){
	for (int i=1;i<=tot;++i) B.a[i][i]=0;
	for (;p;p>>=1){
		if (p&1) B*=A;
		A*=A;
	}
}
int main(){
	cin>>p>>m>>x>>y;
	for (int i=1;i<=m;++i){
		cin>>a[i].len>>a[i].s>>a[i].t;
		b[++tot]=a[i].s;
		b[++tot]=a[i].t;
	}
	sort(b+1,b+1+tot);
	tot=unique(b+1,b+1+tot)-b-1;
	x=lower_bound(b+1,b+1+tot,x)-b;
	y=lower_bound(b+1,b+1+tot,y)-b;
	for (int i=1;i<=m;++i){
		s=lower_bound(b+1,b+1+tot,a[i].s)-b;
		t=lower_bound(b+1,b+1+tot,a[i].t)-b;
		A.a[s][t]=A.a[t][s]=min(A.a[s][t],a[i].len);
	}
	qpow(p);
	cout<<B.a[x][y];
		
	
}