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

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

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

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

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;
        double lg=log((double)c);
        gf[x].push_back(make_pair(y,lg));
        gf[y].push_back(make_pair(x,lg));
    }

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