#include<stdio.h>
#include<stdlib.h>
int a[50000][50001],n;
void roy_floyd()
  {
   for(int k=1;k<=n;++k)
      for(int i=1;i<=n;++i)
         for(int j=1;j<=n;++j)
            if(a[i][k]!=0&&a[k][j]!=0&&(a[i][k]+a[k][j]<a[i][j]||a[i][j]==0)&&i!=j)
              a[i][j]=a[i][k]+a[k][j];
   }
int main()
  {int m,i,x,y,c;
   freopen("dijkstra.in","rt",stdin);
   freopen("dijkstra.out","wt",stdout);
   scanf("%d %d",&n,&m);
   for(i=1;i<=m;++i) scanf("%d %d %d",&x,&y,&c),a[x][y]=c;
   roy_floyd();
   for(i=2;i<=n;++i) printf("%d ",a[1][i]);
   //system("PAUSE");
   return 0;
  }