#include<fstream>
#include<cmath>
#include<vector>
#include<queue>
#define inf 10000005.0
#include<cstring>
#define mod 104659
#define dim 2507
using namespace std;

ifstream f("dmin.in");
ofstream g("dmin.out");
vector<pair <int ,double > > G[dim];
vector<pair <int ,double > > :: iterator it;
int viz[dim],nr[dim];
double  D[dim];
queue<int>Q;
int i,x,y;
double t;
int n,m;
int main () {

    f>>n>>m;

    for(i=1;i<=m;++i){

        f>>x>>y>>t;
        double c=(double )log(t);
        G[x].push_back(make_pair(y,c));
        G[y].push_back(make_pair(x,c));
    }
    memset(D,inf,sizeof(D));
    Q.push(1);
    nr[1]=1;
    D[1]=0;
    viz[1]=1;
     double eps=0.00000001;
    while(!Q.empty()) {
        x=Q.front();
        Q.pop();
        viz[x]=0;
        for(it=G[x].begin(); it!=G[x].end();++it){
            int fiu=(*it).first;
            if( D[fiu]-D[x]-(*it).second>eps ){
                D[fiu]=D[x]+(*it).second;
                nr[fiu]=nr[x];
                if(!viz[fiu]){
                    viz[fiu]=1;
                    Q.push(fiu);
                }
            }
            else {
               if(-D[fiu]+D[x]+(*it).second<=eps){
                    nr[fiu]+=nr[x];
                    nr[fiu]%=mod;
               }
            }
        }
    }
    for(i=2;i<=n;i++){
        g<<nr[i]<<" ";
        }
    return 0;
}