#include <bits/stdc++.h>

#define int long long

using namespace std;

struct littlestar{

    int to;

    int nxt;

    long long w;

}star[];

int head[],cnt;

long long n,m,s,t,p;

inline void add(int u,int v,long long w)

{

    star[++cnt].to=v;

    star[cnt].w=w;

    star[cnt].nxt=head[u];

    head[u]=cnt;

}

bool cmp(littlestar x,littlestar y)

{

    return x.w<y.w;

}

priority_queue<pair<double,int> > q;

int vis[];

double dis[];

long long dis2[];

void dijkstra(int s)

{

    for(int i=;i<=n;i++) dis[i]=99999999.999,dis2[i]=;

    q.push(make_pair(0.00000,s));

    dis[s]=0.0000;

    while(q.size()){

        int u=q.top().second;

        q.pop();

        if(vis[u]) continue;

        vis[u]=;

        for(int i=head[u];i;i=star[i].nxt){

            int v=star[i].to;

            if(dis[v]>dis[u]+(double)log(star[i].w)){

                dis[v]=dis[u]+(double)log(star[i].w);

                dis2[v]=(star[i].w%p*dis2[u])%p;

                q.push(make_pair(-dis[v],v));

            }

        }

    }

}

signed main()

{

    p=;

    cin>>n>>m;

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

        int u,v;

        long long w;

        scanf("%lld%lld",&u,&v);

        cin>>w;

        add(u,v,w);

        add(v,u,w);

    }

    dijkstra();

    cout<<dis2[n]<<" ";

}

/*

3 3 1 3 5

1 2 2

2 3 4

1 3 11

*/