#include <bits/stdc++.h>
#define Vmax 1502
#define Inf 2000000000.0
#define e 0.0000000001
#define pii pair <int, double>
#define pb(x) push_back(x)
#define mod 104659
#define f first
#define s second
FILE *fin  = freopen("dmin.in", "r", stdin);
FILE *fout = freopen("dmin.out", "w", stdout);

using namespace std;
int V, E, sol[Vmax];
double D[Vmax];
struct comp
{
    bool operator() (const pii &a, const pii &b)
    {
        if(fabs(a.s - b.s) < e)
            return 0;
        else return a.s > b.s;
    }
};
priority_queue <pii, vector<pii>, comp> Q;
vector <pii> G[Vmax];
bool F[Vmax];
void read()
{
    int x, y;
    double z;
    scanf("%d %d", &V, &E);
    while(E --)
    {
        scanf("%d %d %d", &x, &y, &z);
        z = log(z);
        G[x].pb(pii(y, z));
        G[y].pb(pii(x, z));
    }
    for(int i = 1; i <= V; ++ i)
        D[i] = Inf;
    D[1] = 0.0;
    Q.push(pii(1, 0.0));
}
void solve()
{
    int x, y;
    double z;
    while(!Q.empty())
    {
        x = Q.top().f;
        Q.pop();
        int sz = G[x].size();
        for(int i = 0; i < sz; ++ i)
        {
            y = G[x][i].f;
            z = G[x][i].s;
            if(!F[y])
            {
                if(D[y] > D[x] + z + e)
                {
                    D[y] = D[x] + z;
                    sol[y] = sol[x];
                    Q.push(pii(y, D[y]));
                }
                else if(fabs(D[y] - D[x] - z) < e)
                    sol[y] = (sol[y] + sol[x]) % mod;
            }
        }
        F[x] = 1;
    }
}
void write()
{
    for(int i = 2; i <= V; ++ i)
        printf("%d", sol[i]);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}