# include <stdio.h>
# define INFI 99999999

int d[5000];
int c[5000][5000],l[5000][5000];
int q[25000];
int i,a,b,co,n,m,in,sf,v,x;

void Bellman();

int main ()
{
  freopen ("bellmanford.in","r",stdin);
  freopen ("bellmanford.out","w",stdout);
  scanf ("%d%d",&n,&m);
  for (i=1;i<=m;i++)
  {
     scanf("%d%d%d",&a,&b,&co);
     l[a][0]++;l[a][l[a][0]]=b;
     c[a][l[a][0]]=co;
    
  }
  Bellman();
  for (i=2;i<=n;i++)
     printf("%d ",d[i]);
printf("\n");
  return 0;
}

void Bellman()
{
     q[0]=1;
     for (i=1;i<=n;i++)
          d[i]=INFI;
     d[1]=0;
     in=0;
     sf=0;
     while (in<=sf)
     {
          x=q[in];
          in++;
          for (v=1;v<=l[x][0];v++)
          if (d[l[x][v]]>d[x]+c[x][v])
          {
               d[l[x][v]]=c[x][v]+d[x];
               sf++;
               q[sf]=l[x][v];
          }
     }
}