#include<iostream>
#include<fstream>
#include<cmath>
#include<vector>
#include<queue>
#define CL 104659
#define epsilon 1e-10
#define Dim 20000000.0
using namespace std;
ifstream fin("dmin.in");
ofstream fout("dmin.out");
double d[1505];
int n,m,per[1505];
vector < pair<int, double> > G[1505];

priority_queue < pair< int,double >, vector< pair< int, float > >, greater < pair < int, double > > > q;

void citire()
{   int i,x,y,z;
    fin>>n>>m;
for (i=1;i<=m;i++)
{
    fin>>x>>y>>z;
    G[x].push_back(make_pair(y,log10(z)));
    G[y].push_back(make_pair(x,log10(z)));

}

}

void dijkstra()
{
    int viz[1605],i;
    for(i=1;i<=n;i++) d[i]=Dim;
    d[1]=0;
    int aux;
    q.push(make_pair(1,d[1]));
    per[1]=1;
    while(!q.empty())
    {
        aux=q.top().first;
        q.pop();
        if(viz[aux]==0)
        {
            viz[aux]=1;
            for( i=0;i<G[aux].size();i++)
            {
                int urm=G[aux][i].first;
                double cost=G[aux][i].second;
                 if(abs(d[urm]-(d[aux]+cost))<=epsilon) per[urm]=(per[urm]+per[aux]) % CL;
                 else if(d[urm]>d[aux]+cost)
                {
                    d[urm]=d[aux]+cost;
                    per[urm]=per[aux];
                    if(viz[urm]==0) q.push(make_pair(urm,d[urm]));
                }


            }
        }
    }
}

void afisare()
{
  int i;
    for(i=2;i<=n;i++)
        fout<<per[i]<<' ';
}
int main()
{
    citire();
    dijkstra();
    afisare();

}