#include<cstdio>
#include<cmath>
#include<set>
#include<vector>
#define MOD 104659
using namespace std;
int n,m;
struct aa
    {int nod,nr;
    double x;

    inline bool operator < (const aa &a) const
        {if( x < a.x || ( x == a.x && nod < a.nod))
            return true;
        return false;
        }
    };
set<aa> s;
vector<pair<int, double> > v[1501];
struct aaa
    {double x;
    int y;
    };
aaa vec[1501];
double modul(double x)
    {if(x >= 0)
        return x;
    else
        return -x;
    }
int main ()
{freopen ("dmin.in","r",stdin);
freopen ("dmin.out","w",stdout);
int i,x,y,z,nod,nr;
double k,val;
aa aux;
scanf("%d%d",&n,&m);
for(i = 1; i <= m; i++)
    {scanf("%d%d%d",&x,&y,&z);
    k = z * 1.0;
    k = log10(k);
    v[x].push_back(make_pair(y,k));
    v[y].push_back(make_pair(x,k));
    }
for(i = 1; i <= n; i++)
    vec[i].x = 1000000000;
vec[1].x = 0;
vec[1].y = 1;
aux.nod = 1;
aux.nr = 1;
aux.x = 0.0;
s.insert(aux);
while(!s.empty())
    {nod = (*s.begin()).nod;
    val = (*s.begin()).x;
    nr = (*s.begin()).nr;
    s.erase(*s.begin());
    for(i = 0; i < v[nod].size(); i++)
        if(modul(val + v[nod][i].second - vec[v[nod][i].first].x) <= 0.0005)
            {vec[v[nod][i].first].y += vec[nod].y;
            vec[v[nod][i].first].y %= MOD;
            aux.nod = v[nod][i].first;
            aux.x = vec[v[nod][i].first].x;
            aux.nr = vec[v[nod][i].first].y;
            s.insert(aux);
            }
        else if(val + v[nod][i].second < vec[v[nod][i].first].x)
            {vec[v[nod][i].first].x = val + v[nod][i].second;
            vec[v[nod][i].first].y = vec[nod].y;
            aux.x = vec[v[nod][i].first].x;
            aux.nr = vec[v[nod][i].first].y;
            aux.nod = v[nod][i].first;
            s.insert(aux);
            }
    }
for(i = 2; i <= n; i++)
    printf("%d ",vec[i].y);
return 0;
}