//dijkstra cu heapuri
#include <fstream>
#include <math.h>
#define epsilon 0.0000000001
#define lg_max 15001
#define MAXM 104659
#define infinit 1<<30
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct nod
{
    int inf;
    double cost;
    nod *next;
} *sir[lg_max];

int heap[lg_max];
double dist[lg_max];
int viz[lg_max];
int n,m,nr;
int numar[lg_max];

void adauga(int a,int b,double c)
{
    nod *q=new nod;
    q->inf=a;
    q->cost=c;
    q->next=sir[b];
    sir[b]=q;
}

void citire()
{
    fin>>n>>m;
    int a,b,cost;
    for (int i=0;i<m;i++)
    {
        fin>>a>>b>>cost;
        adauga(b,a,log(cost));
    }
}

void initializare()
{
    for (int i=1;i<=n;i++)
    {
        heap[i]=i;
        dist[i]=infinit;
        viz[i]=-1;
    }
    nr++;
    dist[1]=0;
    heap[1]=1;
    viz[1]=1;
}

void schimba(int a,int b)
{
    int aux=heap[a];
    heap[a]=heap[b];
    heap[b]=aux;
}

void in_jos(int poz)
{
    while (poz<=nr)
    {
         int c=poz;
         if ((poz<<1)>nr)
             return;
         c=poz<<1;
         if ( c+1<=nr)
             if ( dist[heap[c+1]] < dist[heap[c]])
                 c++;
         if (dist[heap[poz]]<= dist[heap[c]])
             return;
         viz[heap[poz]]=c;
         viz[heap[c]]=poz;
         schimba(poz,c);
         poz=c;
    }

}

void in_sus(int poz)
{
    while (poz>1)
    {
        if (dist[heap[poz]]<dist[heap[poz>>1]])
        {
            viz[heap[poz]]=poz>>1;
            viz[heap[poz>>1]]=poz;
            schimba(poz,poz>>1);
            poz=poz>>1;
        }
        else
            return ;
    }
}

void dijkstra()
{
    int min;
    initializare();
    nr=1;
    numar[1]=1;
    while (nr)
    {
        min=heap[1];
        schimba(1,nr);
        viz[heap[1]]=1;
        nr--;
        in_jos(1);
        for (nod *i=sir[min];i;i=i->next)
            if (dist[i->inf]>dist[min]+i->cost)
            {
                 numar[i->inf]=numar[min];
                 numar[i->inf]%=MAXM;
                dist[i->inf]=dist[min]+i->cost;
                if (viz[i->inf]==-1)
                {
                    nr++;
                    heap[nr]=i->inf;
                    viz[heap[nr]]=nr;
                    in_sus(nr);
                }
                else
                in_sus(viz[i->inf]);
            }
            else
            {
                    if (fabs(dist[i->inf]-dist[min]-i->cost)<epsilon)
                    {
                         numar[i->inf]+=numar[min];
                         numar[i->inf]%=MAXM;
                         nr++;
                         heap[nr]=i->inf;
                         viz[heap[nr]]=nr;
                         in_sus(nr);
                    }
            }
    }
}

void afisare()
{
    for (int i=2;i<=n;i++)
        fout<<numar[i]<<" ";
}

int main ()
{
    citire();
    dijkstra();
    afisare();
    return 0;
}