#include <stdio.h>
#define inf 2000000000

using namespace std;

struct muchie{
              long x,y,c;
              }G[50002];

long D[250002],m,n;
long i,x,y,c,ok;

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

 scanf("%ld %ld", &n, &m);

 for(i=1;i<=m;i++)
   {
    scanf("%ld %ld %ld", &x, &y, &c);
    G[i].x=x;
    G[i].y=y;
    G[i].c=c;
    if(x==1) D[y]=c;
   }

 for(i=2;i<=n;i++)
  if(D[i]==0) D[i]=inf;

 do{
    ok=1;
    for(i=1;i<=m;i++)
      if(D[G[i].y] > D[G[i].x]+G[i].c){
                                       D[G[i].y] = D[G[i].x]+G[i].c;
                                       ok=0;
                                       }
   }while(!ok);

 for(i=2;i<=n;i++)
   if(D[i]!=inf) printf("%ld ", D[i]);
            else printf("0 ");


 return 0;
}