#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("dmin.in");
ofstream g("dmin.out");

#define infinite 100000000

vector <pair <int, int>> a[1501];
queue <int> coada;
bool viz[1501];
int d[1501],rep[1501];
int nodcurent,vecin,i,cost,k1,k2,k3,n,m;

void dijkstra()
{
    while(coada.empty()==0)
    {
        nodcurent=coada.front(); coada.pop();
     //   if(coada.empty()==1)
        //    d[nodcurent]=1;
        for(unsigned int i=0; i<a[nodcurent].size();i++)
        {
            vecin=a[nodcurent][i].first;
            cost=a[nodcurent][i].second;
            if(d[vecin]>d[nodcurent]*cost)
            {
                d[vecin]=d[nodcurent]*cost;
                rep[vecin]=rep[nodcurent];
            }
            else if(d[vecin]==d[nodcurent]*cost)
            {
                rep[vecin]=(rep[vecin]+rep[nodcurent])%104659;
            }
            if(viz[vecin]==0)
            {
                viz[vecin]=1;
                coada.push(vecin);
            }
        }
    }
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>k1>>k2>>k3;
        a[k1].push_back(make_pair(k2,k3));
        a[k2].push_back(make_pair(k1,k3));
    }
    for(i=1;i<=n;i++)
        d[i]=infinite;

    coada.push(1); rep[1]=1; d[1]=1; viz[1]=1;
    dijkstra();
    for(i=2;i<=n;i++)
        g<<rep[i]<<" ";

    return 0;
}