#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#include<stack>

#include<cstdio>

#include<map>

#include<set>

#include<string>

#include<queue>

using namespace std;

#define inf 2147483647

typedef long long ll;

const ll mod=1e9+;

const int maxn=+;

ll dis[maxn];

struct edg{

    int to;

    int w;

};

vector<edg > sm[maxn];

typedef pair<int ,int > P;//最短距离，标点

void dij(int v){

    fill(dis,dis+maxn,-);

    priority_queue<P,vector<P>,greater<P> > que;

    que.push(P(,v));

    P tem;

    dis[v]=;

    while(!que.empty()){

        tem=que.top();

        que.pop();

        int i=tem.second;

        if(tem.first>dis[i])

        continue;

        for(int j=;j<sm[i].size();j++){

            edg e=sm[i][j];

            if(dis[e.to]==-||dis[e.to]>dis[i]+e.w){

                dis[e.to]=dis[i]+e.w;

                que.push(P(dis[e.to],e.to));

            }

        }

    }

}

int main(){

    int n,m,s,t;

    int u,v;

    ll w;

    ll ans=;

    edg tem;

    cin>>n>>m>>s>>t;

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

        cin>>u>>v>>w;

        w=log(w)/log();

        tem.to=v;

        tem.w=w;

        sm[u].push_back(tem);

    }

    dij(s);

    if(dis[t]==-){

        cout<<"-1"<<endl;

    }

    else{

            //cout<<dis[t]<<endl;

        ll tem=;

        while(dis[t]!=){

            if(dis[t]%==){

                ans=(ans*tem)%mod;

            }

            dis[t]/=;

            tem=(tem*tem)%mod;

        }

        cout<<ans<<endl;

    }

    return ;

}