# include <stdio.h>
# include <math.h>
# include <stdlib.h>

# define MAXN 2000
# define INF -1
# define EPS 0.00001

typedef struct {long int n;long int v[MAXN+1];long int index[MAXN+1],roads[MAXN+1];} HEAP;
typedef double TIPD;
typedef struct NOD {long int nod; TIPD dist; NOD* next;} NOD;
typedef struct LISTA {NOD *begin,*end;};
LISTA ladiac[MAXN+1];
TIPD raza[MAXN+1];
long int n,m;

TIPD modul(TIPD a) {if (a<0) return -a; return a;}
long int mai_mare(TIPD a, TIPD b) 
     {
     if (b==INF) return 0; 
     if (a==INF) return 1;
     if (a-b>EPS) return 1; 
     return 0;
     }
long int mai_mic(TIPD a, TIPD b)
     {
     if (a==INF) return 0;
     if (b==INF) return 1;
     if (a-b<-EPS) return 1;
     return 0;
     }
long int egal(TIPD a, TIPD b) 
     {
     if (a==INF || b==INF) return 0;
     if (modul((a-b))<=EPS) return 1; 
     return 0;
     }
long int better(long int a,long int b) {return mai_mic(raza[a],raza[b]);}

void test(HEAP &a);

void rise_heap(HEAP &a, long int i)
{
     long int auxf;
     while (i/2 && better(a.v[i],a.v[i/2]))
           {
            auxf=a.v[i];a.v[i]=a.v[i/2];a.v[i/2]=auxf;
            a.index[a.v[i]]=i;
            a.index[a.v[i/2]]=i/2;
            i/=2;
            }
}

void submerge_heap(HEAP &a, long int i)
{
     long int min=0,auxi;long int auxf;
     while (2*i<=a.n)
           {
           min=i;
           if (2*i  <=a.n && better(a.v[2*i  ],a.v[min])) min=2*i;
           if (2*i+1<=a.n && better(a.v[2*i+1],a.v[min])) min=2*i+1;
           if (min==i) break;
           auxf=a.v[min];a.v[min]=a.v[i];a.v[i]=auxf;
           a.index[a.v[min]]=min;a.index[a.v[i]]=i;
           min=i;
           }
}

void insert_heap(HEAP &a, long int nod)
{
     a.n++;
     a.v[a.n]=nod;
     //a.roads[nod]=0;
     a.index[nod]=a.n;
     rise_heap(a,a.n);
}

long int extract_heap(HEAP &a)
{
     long int sol;
     sol=a.v[1]; a.index[sol]=0;
     
     a.v[1]=a.v[a.n]; a.v[a.n]=0; a.index[a.v[1]]=1; a.n--;
     
     submerge_heap(a,1);
     
     return sol;
}

void create_heap(HEAP &a)
{
     long int i;
     NOD *p;
     a.n=0;
     raza[1]=0;
     a.roads[1]=1;
     a.index[1]=0;  
     for (i=2;i<=n;i++) 
         {
         raza[i]=INF;
         a.roads[i]=0;
         }
     p=ladiac[1].begin;
     while (p)
           {
           raza[(*p).nod]=(*p).dist;
           a.roads[(*p).nod]=1;
           p=(*p).next;
           }
     
     for (i=2;i<=n;i++) 
         insert_heap(a,i);
     //nodul 1 nu este bagat in heap deci trebuie facut manual
     // raza e pusa 0   
}

void insert_list(LISTA &a, long int nod, TIPD dist)
{
     NOD* p=(NOD*) malloc (sizeof(NOD));
     (*p).dist=dist;
     (*p).nod=nod;
     (*p).next=NULL;
     
     if (a.begin==NULL)
        {
        a.begin=a.end=p;
        }
     else
        {
        (*(a.end)).next=p;
        a.end=p;
        }
}
         
void citire()
{
     FILE *f=fopen("dmin.in","r");
     fscanf(f,"%ld%ld",&n,&m);
     long int i,aa,bb;long int dist; //AICI apare tip in loc de TIPD
     for (i=1;i<=m;i++)
         {
         fscanf(f,"%ld%ld%ld",&aa,&bb,&dist);
         insert_list(ladiac[aa],bb,(double)log((float)dist));
         insert_list(ladiac[bb],aa,(double)log((float)dist));
         }             
     fclose(f);
}

void scrie(HEAP &a)
{
     FILE *g=fopen("dmin.out","w");
     long int i;
     for (i=2;i<=n;i++)
         {
         if (i>2) fprintf(g," ");
         fprintf(g,"%ld",a.roads[i]);
         }
     fprintf(g,"\n");
     fclose(g);
}

long int empty(HEAP &a)
{
     if (a.n==0) return 1;
     return 0;
}

void update(HEAP &a, long int nod)
{
     NOD *p;
     p=ladiac[nod].begin;
     while (p)
           {
           //daca prin noua scurtatura obtinem un drum mai bun
           if (mai_mare(raza[(*p).nod],raza[nod]+(*p).dist))
              {
              raza[(*p).nod]=raza[nod]+(*p).dist;
              a.roads[(*p).nod]=a.roads[nod];
              //daca mai e in heap, update; teoretic, ar trebui sa mai fie inca
              if (a.index[(*p).nod]) rise_heap(a,a.index[(*p).nod]);
              }
           else if (egal(raza[(*p).nod],raza[nod]+(*p).dist))
                {
                a.roads[(*p).nod]+=a.roads[nod];
                }
           p=(*p).next;
           }
}
              
void dijkstra(HEAP &a)
{
     //avem heapul gata creat
     //pe rand scoate cate un nod din heap si fa toate update-urile care trebuiesc
     //fiecare nod scos are mereu distanta minima de pana acum. (deci nu se poate ca in viitor 
     //sa dau peste un nod cu distanta mai mica
     long int nod;
     
     while (!empty(a))
           {
           nod=extract_heap(a);
           //fa toate update-urile necesare
           update(a,nod);
           test(a);
           }
}


int main()
{
    HEAP a;
    citire();
    create_heap(a);
    test(a);
    dijkstra(a);
    scrie(a);
    return 0;
}

void test(HEAP &a)
{
     long int i;
     /*printf("%ld%ld",n,m);
     NOD *p;
     for (i=1;i<=n;i++)
         {
         printf("== %ld ==\n",i);
         p=ladiac[i].begin;
         while (p)
               {
               printf("%ld %f | ",(*p).nod,(*p).dist);
               p=(*p).next;
               }
         printf("\n");
         }*/
     for (i=1;i<=n;i++)
         printf("%ld === v[i]=%ld\tindex[i]=%ld\troads[i]=%ld\traza[i]=%f\n",i,a.v[i],a.index[i],a.roads[i],raza[i]);
     getchar();
}