#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#include <cmath>
using namespace std;

#define MOD 104659
#define eps 1e-9

ifstream is ("dmin.in");
ofstream os ("dmin.out");

double D[1505];
int N, M, Nr[1505];

bitset <1505> B;

vector <pair<int, double> > v[1505];

struct CMP{ bool operator ()(int a, int b){   return D[a] > D[b]; }};

priority_queue <int, vector<int>, CMP> Q;

int main()
{
    is >> N >> M;
    for (int i = 2; i <= N; ++i)
        D[i] = (1<<30);
    double cost;
    for (int i = 1, a, b, c; i <= M; ++i)
    {
        is >> a >> b >> c;
        cost = log(c);
        v[a].push_back({b, cost});
        v[b].push_back({a, cost});
    }
    Q.push(1);
    Nr[1] = 1;
    for (int i, nod; !Q.empty(); )
    {
        i = Q.top();
        Q.pop();
        if (B[i])
            continue;
        B[i] = 1;
        for (int j = 0; j < v[i].size(); ++j)
        {
            nod = v[i][j].first;
            cost = v[i][j].second;
            if ( fabs(D[nod] - D[i] - cost) < eps )
                Nr[nod] = (Nr[nod] + Nr[i]) % MOD;
            else
                if (D[nod] > D[i] + cost)
                {
                    Nr[nod] = Nr[i];
                    D[nod] = D[i] + cost;
                    Q.push(nod);
                }
        }
    }

    for (int i = 2; i <= N; ++i)
        os << Nr[i] << ' ';

    is.close();
    os.close();
}