#include<stdio.h>
#define INF 30000
#define nmax 50000

int p[nmax][nmax],d[nmax],viz[nmax];
int n,m;

void read()
{
     int i,j,a,b,c;

     freopen("dijkstra.in","r",stdin);
     freopen("dijkstra.out","w",stdout);

     scanf("%d%d",&n,&m);
     for(i=1;i<=n;++i)
       for(j=1;j<=n;++j)
	 p[i][j]=-1;
     for(i=1;i<=m;++i)
     {
	scanf("%d%d%d", &a,&b,&c);
	p[a][b]=c;
     }
     for(i=1;i<=n;++i)
       for(j=1;j<=n;++j)
	 if(p[i][j]==-1)
	    if(i==j)
	      p[i][j]=0;
	    else
	      p[i][j]=INF;

}


void dijkstra()
{
     int i,j,min,k;
     viz[1]=1;

     for(i=1;i<=n;++i)
       d[i]=p[1][i];
     d[0]=INF;
     for(i=1;i<=n-1;++i)
     {
	 min=INF;
	 k=0;
	 for(j=1;j<=n;++j)
	   if(d[j]<min&&viz[j]==0)
	   {
	     min=d[j];
	     k=j;
	     viz[j]=1;
	   }
	 for(j=1;j<=n;++j)
	   if(d[j]>d[k]+p[k][j])
		d[j]=d[k]+p[k][j];
    }
}

void print()
{
   int i;
   for(i=2;i<=n;i++)
    if(d[i]!=INF)
     printf("%d ",d[i]);
    else
     printf("0 ");
   printf("\n");
}

int main()
{
   read();
   dijkstra();
   print();
   return 0;
}