#include <bits/stdc++.h>

using namespace std;

#define lowbit(x) (x&(-x))

#define IL inline

#define rint register int

#define me(x) memset(x,0,sizeof(x))

#define fi first

#define se second

#define mid ((h+t)/2)

#define rep(i,h,t) for (rint i=h;i<=t;i++)

#define dep(i,t,h) for (rint i=t;i>=h;i--)

#define setit set<int>::iterator

const int INF=1e9;

char ss[<<],*A=ss,*B=ss;

IL char gc()

{

  return A==B&&(B=(A=ss)+fread(ss,,<<,stdin),A==B)?EOF:*A++;

}

template<class T>void read(T &x)

{

  rint f=,c; while (c=gc(),c<||c>) if (c=='-') f=-; x=c^;

  while (c=gc(),<c&&c<) x=(x<<)+(x<<)+(c^); x*=f;

}

int n,m,s,t,cnt;

struct re{

  int d[][];

}ys;

re js(re x,re y)

{

  re ans;

  rep(i,,)

    rep(j,,)

      ans.d[i][j]=INF;

  rep(k,,cnt)

    rep(i,,cnt)

      rep(j,,cnt)

        ans.d[i][j]=min(ans.d[i][j],x.d[i][k]+y.d[k][j]);

  return(ans);

}

re qpow(int x)

{

  if (x==) return(ys);

  re y=qpow(x/);

  y=js(y,y);

  if (x%) y=js(y,ys);

  return(y);

}

int main()

{

  freopen("1.in","r",stdin);

  freopen("1.out","w",stdout);

  read(n); read(m); read(s); read(t);

  rep(i,,)

    rep(j,,)

      ys.d[i][j]=INF;

  map<int,int>M;

  rep(i,,m)

  {

    int x,y,z;

    read(x); read(y); read(z);

    int x1,x2;

    if (!M[y]) x1=M[y]=++cnt; else x1=M[y];

    if (!M[z]) x2=M[z]=++cnt; else x2=M[z];

    ys.d[x1][x2]=min(ys.d[x1][x2],x);

    ys.d[x2][x1]=min(ys.d[x2][x1],x);

  }

  re ans=qpow(n);

  printf("%d",ans.d[M[s]][M[t]]);

  return ;

}