#include <fstream>
#include <queue>
#include <vector>
#include <cmath>
#define NMAX 1501
#define MMAX 2501
#define INF 999999999
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
struct foo{
    int x;
    double c;
}A[NMAX][NMAX];
int d[NMAX],uz[NMAX],n,m;
queue<int> Q;
double dmin[NMAX];
int nrd[NMAX];
const double EPS=1e-9;
void citire();
void BellmanFord();
void afisare();
int main()
{
    citire();
    BellmanFord();
    return 0;
}
void citire()
{
    int i,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        d[x]++;
        A[x][d[x]].x=y;
        A[x][d[x]].c=c;
        d[y]++;
        A[y][d[y]].x=x;
        A[y][d[y]].c=c;
    }
}
void BellmanFord()
{
    int x,i,vecin,cost;
    for(i=2;i<=n;i++)
        dmin[i]=INF;
    Q.push(1);
    nrd[1]=1;
    uz[1]=1;
    while(!Q.empty())
    {
        x=Q.front();Q.pop();uz[x]=0;
        for(i=1;i<=d[x];i++)
        {
            vecin=A[x][i].x;
            cost=log10(A[x][i].c);
            if(dmin[vecin]>dmin[x]+cost+EPS)
            {
                dmin[vecin]=dmin[x]+cost+EPS;
                nrd[vecin]=nrd[x]%104659;
                if(!uz[vecin])
                {
                    uz[vecin]=1;
                    Q.push(vecin);
                }
            } else if(abs(dmin[vecin]-dmin[x]-cost)<EPS)
            {
                nrd[vecin]=(nrd[vecin]%104659+nrd[x]%104659)%104659;

            }
        }
    }
}
void afisare()
{
    int i;
    for(i=2;i<=n;i++)
        fout<<nrd[i];
}