#include<fstream>
#include<vector>
#include<set>
#include<queue>
#include<cmath>

using namespace std;

ifstream fin("dmin.in");
ofstream fout("dmin.out");

#define pb push_back
#define NMAX 1503
#define MMAX 2506
#define INF (1<<30);
#define mp make_pair
#define MOD 104659
#define EPS 0.0000001
int n, m;
vector <pair <int, double> > g[NMAX];
queue < int >q;
bool use[NMAX];
void read(){
    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        int x, y;
        double c;
        fin >>x >>y >>c;
        c = log(c);
        g[x].pb(mp(y,c));
        g[y].pb(mp(x,c));
        //fout << c <<'\n';
    }
}

void Dijkstra(int r){
    int nr_drumuri[NMAX];
    double dist[NMAX];
    for(int i = 1; i <= n; i++) nr_drumuri[i] = 0, dist[i] = INF;

    dist[r] = 0;
    q.push(r);
    nr_drumuri[r] = 1;
    use[r] = true;
    while(! q.empty()){
        int nod = q.front();
        q.pop();
        use[nod] = false;

        for(int i = 0 ; i < g[nod].size(); i++){
            double cost = g[nod][i].second;
            int y = g[nod][i].first;
             if(fabs (dist[y] -  dist[nod] -  cost) < EPS ){
                nr_drumuri[y] = (nr_drumuri[y] + nr_drumuri[nod] ) %MOD;
            }
            if(dist[y] -  dist[nod] - cost>EPS ){

                if(use[y] == false)
                    q.push(y), use[y] = true;
                dist[y] = dist[nod] + cost;
                nr_drumuri[y] = nr_drumuri[nod] %MOD;
            }


        }
    }
    for(int i = 2; i<= n ;i++)
        fout << nr_drumuri[i] <<" ";
}
int main(){
    read();
    Dijkstra(1);
    fin.close();
    return 0;

}