/**
    Multumesc Narci6ix
*/
#include<bits/stdc++.h>
#define eps 1e-9
#define MOD 104659
#define INF INT_MAX
#define maxN 1505
using namespace std;
double dp[maxN];
vector<pair<int,double> > v[maxN];
int pos[maxN],n,m,x,y,c;
typedef struct edge
{
  int nod;
  double cost;
  bool operator<(const edge& other) const
  {
    return cost>other.cost;
  }
};
priority_queue<edge> q;
void Dijkstra()
{
    while(!q.empty())
    {
        int x=q.top().nod;
        double y=q.top().cost;
       // if(dp[x]<y) continue;
        q.pop();
        for(vector<pair<int,double> >::iterator it=v[x].begin();it!=v[x].end();it++)
        {
            double newcost=y+(*it).second;
            if((dp[(*it).first]-eps)>newcost)
            {
                dp[(*it).first]=newcost;
                pos[(*it).first]=pos[x];
                q.push({(*it).first,dp[(*it).first]});
            }
                else
            if(fabs(newcost-dp[(*it).first])<=eps)
            {
                pos[(*it).first]=(pos[(*it).first]+pos[x])%MOD;
            }
        }
    }
}
int main()
{
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(make_pair(y,log2(c)));
        v[y].push_back(make_pair(x,log2(c)));
    }
    dp[1]=0;
    for(int i=2;i<=n;i++) dp[i]=1.0*INF;
    pos[1]=1;
    q.push({1,0});
    Dijkstra();
    for(int i=2;i<=n;i++) printf("%d ",pos[i]);
    return 0;
}