#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

inline int read()

{

	int x=0,t=1;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=-1,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return x*t;

}

//map<int,int> M;

int M[1000100];

int tot,n;

int K,m,S,T;

int Get(int x)

{

	if(M[x])return M[x];

	return M[x]=++tot;

}

struct Dalao

{

	int s[210][210];

	int* operator [](int x){return s[x];}

	void clear(){memset(s,63,sizeof(s));}

}ed,ans;

Dalao operator *(Dalao a,Dalao b)

{

	Dalao ret;ret.clear();

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			for(int k=1;k<=n;++k)

				ret[i][k]=min(ret[i][k],a[i][j]+b[j][k]);

	return ret;

}

int main()

{
	freopen("relay.in","r",stdin);
	freopen("relay.out","w",stdout);
	ed.clear();

	K=read();m=read();S=read();T=read();

	for(int i=1;i<=m;++i)

	{

		int W,u,v;

		scanf("%d%d%d",&W,&u,&v);

		//int W=read(),u=read(),v=read();

		u=Get(u);v=Get(v);

		ed[u][v]=ed[v][u]=min(ed[u][v],W);

	}

	n=tot;

	ans.clear();

	for(int i=1;i<=n;++i)ans[i][i]=0;

	while(K)

	{

		if(K&1)ans=ans*ed;

		ed=ed*ed;

		K>>=1;

	}

	printf("%d\n",ans[Get(S)][Get(T)]);

}