#include <fstream>
#include <cmath>
#include <queue>
#include <iomanip>

#define input "dmin.in"
#define output "dmin.out"
#define e 2.718281828459045
#define NMAX 1505
#define DMAX 5000005
#define MOD 104659

using namespace std;
typedef long double ld;

ifstream in(input);
ofstream out(output);

struct muchie
{
    int y; int cost;
};
vector < muchie > muchii[NMAX];
queue < int > coada;

bool OK(ld v)
{
    if(v <= 0.0000000001) return true;
    return false;
}

int N, M, sol[NMAX];
ld dist[NMAX];
bool uz[NMAX];

void Read_Data()
{
    in >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        muchii[x].push_back({y, c});
        muchii[y].push_back({x, c});
    }
}

void Solve()
{
    for(int i = 1; i <= N; i++)
        dist[i] = DMAX;
    dist[1] = 0;
    coada.push(1);
    uz[1] = true;
    sol[1] = 1;
    while(!coada.empty())
    {
        int nod = coada.front(); coada.pop();  uz[nod] = false;
        ld dist_nod = dist[nod];
        for(unsigned i = 0; i < muchii[nod].size(); i++)
        {
            ld dist_muchie = log(muchii[nod][i].cost);
            int new_nod = muchii[nod][i].y;
            ld dist_new = dist[new_nod];
            if(dist_nod + dist_muchie < dist_new)
            {
                dist_new = dist_nod + dist_muchie;
                dist[new_nod] = dist_new;
                sol[new_nod] = sol[nod];
                if(!uz[new_nod])
                {
                    coada.push(new_nod);
                    uz[new_nod] = true;
                }
            }
            else
            {
                if(OK(dist_nod + dist_muchie - dist_new))
                {
                    sol[new_nod] = (sol[new_nod] + sol[nod]) % MOD;
                }
            }

        }
    }
    for(int i = 2; i <= N; i++)
        out << sol[i] << " ";
    out << "\n";
}

int main()
{
    Read_Data();
    Solve();
    return 0;
}