离谱

#include <string.h>
#include <iostream>
using namespace std;
#define int long long
const int N=205;
int n=0,tmp,t,s,e,inf=1e16;
int num[1005];
struct marx{
	int d[N][N];
};
marx mul(marx a,marx b){
	marx s;
	for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) s.d[i][j]=inf;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			for(int k=1;k<=n;++k)	
				s.d[i][j]=min(s.d[i][j],a.d[i][k]+b.d[k][j]);
	return s;
}

signed main(){
	scanf("%lld%lld%lld%lld",&tmp,&t,&s,&e);
	marx a,b;
	memset(a.d,0x3f,sizeof a.d);
//	for(int i=1;i<=200;++i) for(int j=1;j<=200;++j) a.d[i][j]=b.d[i][j]=inf;
//	for(int i=1;i<=200;++i) a.d[i][i]=b.d[i][i]=0;
	for(int i=1;i<=t;++i){
	    int w,u,v; scanf("%lld%lld%lld",&w,&u,&v);
	    if(!num[u]) num[u]=++n; //离散化
	    if(!num[v]) num[v]=++n;
		a.d[num[u]][num[v]]=a.d[num[v]][num[u]]=w;
	}
	--tmp; b=a;
	while(tmp){
		if(tmp&(int)1) a=mul(a,b);
		b=mul(b,b);
		tmp>>=1;
	}
	printf("%lld\n",a.d[num[s]][num[e]]);
}