#include<fstream>
#include<vector>
#include<algorithm>
#include<set>
#include<cmath>

using namespace std;
#define pb push_back
#define mp make_pair
#define Nmax 1504
#define inf 1e9
#define mod 104659
#define eps 1e-9
int n,m,i,a,b,c;
vector< pair < int, double> > g[Nmax];
set< pair < double, int > > s;
vector<double> d(Nmax,inf);
vector<int> p(Nmax,0);

ifstream cin("dmin.in");
ofstream cout("dmin.out");

int main()
{
    cin>>n>>m;
    while  (m--)cin>>a>>b>>c,g[a].pb(mp(b,log(c))),g[b].pb(mp(a,log(c)));
    d[1]=0;
    s.insert(mp(0,1));
    p[1]=1;
    while (s.size())
    {
        int v=s.begin()->second;
        s.erase(s.begin());
        for (i=0;i<g[v].size();i++)
        {
            int to=g[v][i].first; double len=g[v][i].second;
            if (abs(d[v]+len-d[to])<eps){ p[to]+=p[v]; p[to]%=mod; continue;}
            if (d[v]+len>d[to]) continue;
            s.erase(mp(d[to],to));
            d[to]=d[v]+len;
            p[to]=p[v]; p[to]%=mod;
            s.insert(mp(d[to],to));
        }
    }
    for (i=2;i<=n;i++)cout<<p[i]<<' ';
    return 0;
}