#include <fstream>
#include <set>
using namespace std;
ifstream f("dmin.in");
ofstream g("dmin.out");

#include <vector>
#include <cmath>
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define LE 1666
#define eps 0.0000000001
#define double long double

struct comp
{
    bool operator()(pair<pair<int,int>,double> i1 ,pair<pair<int,int>,double> i2 )
    {
        return i1.y<i2.y;;
    }
};
multiset < pair<pair<int,int>,double>,comp> Heap;

vector<pair<int,double> > H[LE];
int n,m,i,xx,yy,j,cost;
int pos[LE];
double dp[LE];
bool viz[LE];

double mdl(double value)
{
    if (value<0)
        return -value;
    else
        return value;
}

bool equal(double AA,double BB)
{
    if (mdl(AA-BB)<=eps)
        return true;

    return false;
}

int main()
{
    f>>n>>m;

    for(i=1; i<=m; ++i)
    {
        f>>xx>>yy>>cost;
        double cost2=log10((double)cost);
        H[xx].pb(mp(yy,cost2));
        H[yy].pb(mp(xx,cost2));
    }

    pos[1]=1;
    Heap.insert(mp(mp(1,1),0));

    while (Heap.empty()==false)
    {
        pair<pair<int,int>,double> next=*(Heap.begin());
        Heap.erase(Heap.begin());

        if(next.x.y!=1)
            if (equal(dp[(next.x).y],next.y)==true||viz[next.x.y]==false)
            {
                pos[(next.x).y]+=pos[(next.x).x];
                pos[(next.x).y]%=104659;
            }
        if (viz[next.x.y]==true)
            continue;

        viz[next.x.y]=true;
        dp[next.x.y]=next.y;

        int N=H[next.x.y].size();

        for( i=0; i<N; ++i)
            Heap.insert(mp( mp(next.x.y,H[next.x.y][i].x),next.y+H[next.x.y][i].y ));
    }

    for(i=2; i<=n; ++i)
        g<<pos[i]<<" ";

    g<<'\n';

    f.close();
    g.close();
    return 0;
}