#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000010
#define mod 9987
#define maxn 9999999
using namespace std;
queue<int>q;
bool vis[N];
int n,m,x,y,z,tot;
int f[N],to[N],dis[N],next[N],head[N];
int read()
{
    ,f=; char ch=getchar();
    ;ch=getchar();}
    +ch-',ch=getchar();
    return x*f;
}
int add(int x,int y,int z)
{
    tot++;
    to[tot]=y;
    dis[tot]=z;
    next[tot]=head[x];
    head[x]=tot;
}
int spfa(int s)
{
    ;i<=n;i++) f[i]=maxn,vis[i]=false;
    f[s]=,vis[s]=,q.push(s);
    while(!q.empty())
    {
        x=q.front(),q.pop();vis[x]=false;
        for(int i=head[x];i;i=next[i])
        {
            int t=to[i];
            if(f[t]>1ll*f[x]*dis[i]%mod)
            {
                f[t]=1ll*f[x]*dis[i]%mod;
                if(!vis[t])
                 q.push(t),vis[t]=true;
            }
        }
    }
}
int main()
{
    n=read(),m=read();
    ;i<=m;i++)
    {
        x=read(),y=read(),z=read();
        add(x,y,z);
    }
    spfa();
    printf("%d",f[n]);
    ;
}