rt.

本地缓存溢出了

#include <bits/stdc++.h>
#define int long long

using namespace std;
template <typename Tp>
inline void read(Tp &x){
    Tp res = 0,f = 1;
    char ch = getchar();
    while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}
    while(isdigit(ch)){res = (res << 1) + (res << 3) + (ch ^ 48);ch = getchar();}
    x = res * f;
}

const int maxn = 1005,inf = 0x3f3f3f3f;
int n,t,s,e,apr[maxn],idx;

struct Matrix{
    int mat[maxn][maxn];
    Matrix(){memset(mat,inf,sizeof(mat));}
    Matrix operator * (const Matrix &g) const{
        Matrix ret;
        for(int k = 1;k <= idx;k ++){
            for(int i = 1;i <= idx;i ++){
                for(int j = 1;j <= idx;j ++){
                    ret.mat[i][j] = min(ret.mat[i][j],g.mat[i][k] + mat[k][j]);
                }
            }
        }
        return ret;
    }
}Ans;

Matrix mat_qpow(Matrix x,int k){
    Matrix ret;
    ret = x,k --;
    while(k){
        if(k & 1) ret = ret * x;
        x = x * x;
        k >>= 1;
    }
    return ret;
}

signed main(){
    read(n),read(t),read(s),read(e);
    for(int i = 1;i <= t;i ++){
        int w,u,v;
        read(w),read(u),read(v);
        if(!apr[u]) apr[u] = ++ idx;
        if(!apr[v]) apr[v] = ++ idx;
        Ans.mat[apr[u]][apr[v]] = Ans.mat[apr[v]][apr[u]] = w;
    }
    Ans = mat_qpow(Ans,n);
    printf("%lld\n",Ans.mat[apr[s]][apr[e]]);
    return 0;
}