#include <fstream>
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
#define STDIN 0
#if STDIN
    #define fein cin
    #define fout cout
#else
    ifstream fein("dmin.in");
    ofstream fout("dmin.out");
#endif

const int NMAX=1501;
const int PRIMEMAX=1e9+1;
const double INF = 1e9+1;
const int MOD = 104659;
const double EPS=1e-5;

int n, m;

struct edge {
    double cost;
    int node;
    const bool operator<(const edge &other) const {
        return cost>other.cost;
    }
};
vector<edge> l[NMAX];

void dijkstra(int start) {
    vector<double> dist(n+1, INF);
    vector<int> ways(n+1, 0);
    priority_queue<edge> q;

    q.push({0, start});
    dist[start]=0;
    ways[start]=1;
    while(!q.empty()) {
        int nc=q.top().node;
        double cc=q.top().cost;
        q.pop();

        if(cc>dist[nc]+EPS) {
            continue;
        }

        for(edge e : l[nc]) {
            double new_cost=e.cost+dist[nc];
            int vc=e.node;
            if(new_cost+EPS<dist[vc]) {
                dist[vc]=new_cost;
                ways[vc]=ways[nc];
                q.push({dist[vc], vc});
            }
            else if(fabs(new_cost-dist[vc])<EPS) {
                ways[vc]=(ways[nc]+ways[vc])%MOD;
            }
        }
    }
    for(int i=2;i<=n;i++) {
        fout<<ways[i]<<" ";
    }
}
void read_data() {
    int a, b;
    double c;
    fein>>n>>m;
    for(int i=1;i<=m;i++) {
        fein>>a>>b>>c;
        l[a].push_back({log(c), b});
        l[b].push_back({log(c), a});
    }
}
int main()
{
    read_data();
    dijkstra(1);
    return 0;
}