/**
    Multumesc Narci6ix
*/
#include<bits/stdc++.h>
#define eps 1e-8
#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;
        q.pop();
        for(vector<pair<int,double> >::iterator it=v[x].begin();it!=v[x].end();it++)
        {
            if((dp[it->first]-eps)>=y+it->second)
            {
                dp[it->first]=y+it->second;
                pos[it->first]=pos[x];
                q.push({it->first,dp[it->first]});
            }
                else if(fabs(it->second+y-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,log10(c)));
        v[y].push_back(make_pair(x,log10(c)));
    }
    dp[1]=0;
    pos[1]=1;
    for(int i=2;i<=n;i++) dp[i]=INF;
    q.push({1,0});
    Dijkstra();
    for(int i=2;i<=n;i++) printf("%d ",pos[i]);
    return 0;
}