#include<cstdio>
const int P=104659,N=1501,M=1<<30;
FILE *in=fopen("dmin.in","r"),*out=fopen("dmin.out","w");
struct graf
{int nod,cost;
graf *next;};
int n,m,d[N],h[N],p[N],k,b[N];
graf *a[N];

void add(int e,int b,int c)
{graf *q=new graf;
q->nod=b,q->cost=c,q->next=a[e],a[e]=q;}

void read()
{fscanf(in,"%d%d",&n,&m);
int x,y,z;
while(m--)
    fscanf(in,"%d%d%d",&x,&y,&z),add(x,y,z);}

void swap(int x,int y)
{int t=h[x];
h[x]=h[y],h[y]=t;}

void upheap(int b)
{int t;
while(b>1)
    {t=b>>1;
    if(d[h[t]]>d[h[b]])
         p[h[b]]=t,p[h[t]]=b,swap(t,b),b=t;
    else
         b=1;}}

void downheap(int b)
{int f;
while(b<=k)
    {f=b;
    if((b<<1)<=k)
         {f=b<<1;
         if(f<k&&d[h[f+1]]<d[h[f]])
               ++f;}
    else
         return;
    if(d[h[b]]>d[h[f]])
         p[h[b]]=f,p[h[f]]=b,swap(b,f),b=f;
    else
         return;}}

void dijkstra_heap()
{for(int i=2;i<=n;++i)
    d[i]=M,p[i]=-1;
p[1]=h[++k]=b[1]=1;
while(k)
    {int min=h[1];
    swap(1,k),p[h[1]]=1,--k,downheap(1);
    graf *q=a[min];
    while(q)
        {if(d[q->nod]>=d[min]+q->cost)
               {if(d[q->nod]==d[min]+q->cost)
                     {b[q->nod]+=b[min];
                     if(b[q->nod]>P)
                            b[q->nod]-=P;}
               else
                     d[q->nod]=d[min]+q->cost,b[q->nod]=b[min];
               if(p[q->nod]!=-1)
                     upheap(p[q->nod]);
               else
                     h[++k]=q->nod,p[h[k]]=k,upheap(k);}
        q=q->next;}}}

int main()
{read(),dijkstra_heap();
for(int i=2;i<=n;++i)
    fprintf(out,"%d ",b[i]);
return 0;}