#include <iostream>
#include <bits/stdc++.h>
#define Nmax 1503
#define mod 104659
#define e 0.00000001
#define INF 100000000.0

using namespace std;

ifstream f ("dmin.in");
ofstream g ("dmin.out");
long double d[Nmax],c,cost;
int n,m,i,x,y, nrDrum[Nmax],nod,next_nod,l;
vector < pair < int,int > > v[Nmax];
set < pair < long double,int > > heap;

int main()
{
    f >> n >> m;
    for(i = 1;i <= m;i++)
    {
        f >> x >> y >> c;
        v[x].push_back({y,c});
        v[y].push_back({x,c});
    }

    for(i = 1;i <= n;i++)
        d[i] = INF;

    heap.insert({0,1});
    d[1] = 0;
    nrDrum[1] = 1;


    while(not heap.empty())
    {
        nod = heap.begin() -> second;
        c = heap.begin() -> first;
        heap.erase(heap.begin());
        l = v[nod].size();
        for(i = 0;i < l;i++)
        {
            next_nod = v[nod][i].first;
            cost = log10(v[nod][i].second);

            if(abs(d[next_nod] - cost - d[nod]) <= e)
                nrDrum[next_nod] = (nrDrum[nod] + nrDrum[next_nod]) % mod;
            else
            if(d[next_nod] + e > d[nod] + cost)
            {
                if(abs(d[next_nod] - INF) > e)
                heap.erase(heap.find({d[next_nod],next_nod}));

                d[next_nod] = d[nod] + cost;
                heap.insert({d[next_nod],next_nod});
                nrDrum[next_nod] = nrDrum[nod];
            }
        }
    }

    for(i = 2;i <= n;i++)
        g << nrDrum[i] << " ";
    return 0;
}