#include <stdio.h>
#include <algorithm>
#define inf 2000000000
#define nMax 50005
#define mMax 250005

using namespace std;

long d[nMax];
long q[nMax];
long poz[nMax];
long n,m,k,i,j,r;
long nod_min,C;
long x[mMax],y[mMax],z[mMax],G[nMax];
long *v[nMax],*c[nMax];
long p[nMax];

void scufunda(long i){
     long fiu;
     while ((long)(i<<1)<=k){
           fiu=i<<1;
           if ((long)(fiu|1)<=n)
              if (d[q[fiu|1]]<d[q[fiu]])fiu|=1;
           if (d[q[fiu]]<d[q[i]]){
              swap(q[i],q[fiu]);
              poz[q[i]]=i;
              poz[q[fiu]]=fiu;
              i=fiu;
           }
           else break;
     }
}

void ridica(long i){
     long val=q[i];
     while (i>1 && d[val]<d[q[i>>1]]){
           q[i]=q[i>>1];
           poz[q[i]]=i;
           i>>=1;
     }
     q[i]=val;
     poz[q[i]]=i;
}

long get_min(){
     swap(q[1],q[k]);
     poz[q[1]]=1;
     poz[q[k]]=k;
     k--;
     scufunda(1);
     return q[k+1];
}

void output(){
     for (i=2;i<=n;i++)
         printf("%ld ",p[i]);
    printf("\n");
}

void dijkstra(){
     //initializare
     for (i=1;i<=n;i++){
         poz[i]=q[i]=i;
         d[i]=inf;
     }
     d[r]=0;
     p[r]=1;
     k=n;
     while (k){
           nod_min=get_min();
           for (i=1;i<=G[nod_min];i++)
               if (d[j=v[nod_min][i]]>d[nod_min]+c[nod_min][i]){
                  d[j]=d[nod_min]+c[nod_min][i];
                  p[j]=p[nod_min];
                  ridica(poz[j]);
               }
               else if (d[j]==d[nod_min]+c[nod_min][i])p[j]+=p[nod_min];
     }
     output();
}

int main(){
    freopen("dmin.in","r",stdin);
    freopen("dmin.out","w",stdout);

    scanf("%ld %ld",&n,&m);
    r=1;//nod sursa
    i=m;
    while (m){
        scanf("%ld %ld %ld",&x[m],&y[m],&z[m]);
        G[x[m]]++;
        m--;
    }
    m=i;
    for (i=1;i<=n;i++){
        v[i]=new long [G[i]+1];
        c[i]=new long [G[i]+1];
        G[i]=0;
    }
    for (i=1;i<=m;i++){
        v[x[i]][++G[x[i]]]=y[i];
        c[x[i]][G[x[i]]]=z[i];
    }

    dijkstra();

return 0;
}