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

#define in "dmin.in"
#define out "dmin.out"
#define LL long long
#define Max_Size 1509
#define Mod 104659
#define oo (1 << 30)
#define eps 1e-10

typedef std :: pair < int, double > NOD;

std :: ifstream f(in);
std :: ofstream g(out);

int N, M, Count[Max_Size];
double D[Max_Size];

std :: vector < NOD > V[Max_Size];
std :: set < NOD >    H;

inline void Read_Data() {
    f >> N >> M;

    double cost;
    for(int i = 1, x, y; i <= M; ++i) {
        f >> x >> y >> cost;
        cost = log(cost);
        V[x].push_back(std :: make_pair(y, cost));
        V[y].push_back(std :: make_pair(x, cost));
    }
}

inline double modul(double a) {
    if(a < 0) a *= -1.0;
    return a;
}

void Djikstra() {
    H.insert( {1, 0} );

    while(!H.empty()) {
        NOD nod = *H.begin();
        H.erase( *H.begin() );

        for(auto val : V[nod.first])
            if(D[val.first] - val.second - nod.second > eps) {
                Count[val.first] = Count[nod.first] % Mod;
                H.erase( {val.first, D[val.first]} );

                D[val.first] = nod.second + val.second;
                H.insert( {val.first, D[val.first]} );
            }   else if(modul(D[val.first] - nod.second - val.second) < eps)
                        Count[val.first] = (Count[val.first] + Count[nod.first] ) % Mod;

    }
}

int main() {
    Read_Data();

    for(int i = 2; i <= N; ++i) D[i] = oo;
    Count[1] = 1;
    Djikstra();

    for(int i = 2; i <= N; ++i) g << Count[i] << ' ';

    g.close();
    return 0;
}