#include <fstream>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#define nmax 1501
#define x first
#define y second
#define inf 987654321
#define MOD 104659
#define eps 1e-9

using namespace std;

typedef vector<pair<int,double> >::iterator it;

vector<pair<int,double> > gf[nmax];
int rez[nmax], n, m;
double d[nmax];
set <pair<double,int> > h;

void dijkstra(){
    for (int i=1; i<=n; i++) d[i] = inf;
    rez[1]=1;
    for(h.insert(make_pair(0,1)); h.size(); h.erase(h.begin())){
        double min = h.begin()->x;
        int nod = h.begin()->y;
        for(it i=gf[nod].begin(); i!=gf[nod].end(); i++){
            int vecin = i->x;
            double cost = i->y;
            if ( fabs(d[vecin] - min - cost ) < eps ) rez[vecin] = (rez[vecin] + rez[nod]) % MOD;
            else if(d[vecin] > min + cost){
                d[vecin] = min + cost;
                rez[vecin] = rez[nod];
                h.insert(make_pair(d[vecin], vecin));
            }
        }
    }
}

int main(){
    ifstream f("dmin.in");
    ofstream g("dmin.out");
    f>>n>>m;
    for(int i=1; i<=m; i++){
        int x, y, c;
        f>>x>>y>>c;
        gf[x].push_back(make_pair(y,log(c)));
        gf[y].push_back(make_pair(x,log(c)));
    }

    dijkstra();
    for(int i=2; i<=n; i++) g<<rez[i]<<" ";
    return 0;
}