#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <math.h>
#include <queue>
#include <stdlib.h>
#define inf (1<<30)
#define mod 104659
#define EPS 0.0000000001
using namespace std;
ifstream in("dmin.in");
ofstream out("dmin.out");
vector < pair <int , double> > A[1505];
double c,dis[1505];
long long drum[1505];
int x,y,i,n,m,nodcurent;
queue < int > coada;
bitset <1505> viz;




int main()
{
    in>>n>>m;
    for(i=0;i<m;++i){
        in>>x>>y>>c;
        c=log10(c);
        A[x].push_back({y,c});
        A[y].push_back({x,c});
    }
    for(i=2;i<=n;++i){
        dis[i]=inf;
    }
    coada.push(1);
    dis[1]=0;
    drum[1]=1;
    viz[1]=1;

    vector < pair <int , double> > ::iterator it;
    while(!coada.empty()){

            nodcurent = coada.front();
            coada.pop();
            viz[nodcurent]=0;
    for( it=A[nodcurent].begin() ; it!=A[nodcurent].end()  ; ++it )
        {

        if(dis[it->first] - EPS > (it->second+dis[nodcurent]))
        {
            dis[it->first]= (it->second+dis[nodcurent]);
            drum[it->first]=drum[nodcurent];
            if(!viz[it->first]) viz[it->first]=1 , coada.push(it->first);

        }
        else if(abs(dis[it->first] < (it->second + dis[nodcurent] )) < EPS ){
            drum[it->first] += drum[nodcurent];
            if(drum[it->first]>= mod) drum[it->first] -= mod;
            if(!viz[it->first]) viz[it->first]=1 , coada.push(it->first);

        }

    }
    }


    for(i=2;i<=n;++i) out<<drum[i]<<' ';

        return 0;
}