求帮qwq

#include<bits/stdc++.h>
using namespace std;
//const int M=1000;
struct matrux{
	int m[1010][1010];
	matrux(){memset(m,0,sizeof(m));}
}t;
int n=1000,m,tx;
int S,T;
matrux operator*(const matrux&a,const matrux&b){
	matrux c;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++){
				if(a.m[i][k]!=0&&b.m[k][j]!=0) c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]);
			}
		}
	}
	return c;
}
matrux pow_matrux(matrux a,int b){
	matrux ans;
	for(int i=0;i<=n;i++) ans.m[i][i]=1;
	while(b){
		if(b&1) ans=ans*a;
		a=a*a;
		b>>=1;
	}
	return ans;
}
int main(){
//	ios::sync_with_stdio(0);
//	cin.tie(0); cout.tie(0);
	cin>>tx>>m>>S>>T;
	for(int i=1;i<=1000;i++){
		for(int j=1;j<=1000;j++) t.m[i][j]=1010;
	}
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>w>>u>>v;
		t.m[u][v]=min(t.m[u][v],w);
		t.m[v][u]=min(t.m[v][u],w);
	}
	cout<<pow_matrux(t,tx).m[S][T];
	return 0;
}