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


queue < int > coada;
void Dijkstra ( int sursa ){
    for(i=2;i<=n;++i){
        dis[i]=inf;
    }
    coada.push(sursa);
    dis[sursa]=0;
    drum[sursa]=1;
    viz[sursa]=1;

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

            int 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]=true;
                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]==0){
                viz[it->first]=true;
                coada.push(it->first);
            }
        }

    }
    }

}

int main()
{
    in>>n>>m;
    for(i=1;i<=m;++i){
        in>>x>>y>>c;
        c=log10(c);
        A[x].push_back(make_pair(y,c));
        A[y].push_back(make_pair(x,c));
    }
    Dijkstra(1);

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

        return 0;
}