#include<stdio.h>
#include<stdlib.h>
#define N 50001
typedef struct nod
{long info;
struct nod *next;}Nod;
typedef struct
{Nod *prim,*ultim;}queue;
typedef struct list
{long x,y;
struct list *urm;};

void add(list *&l,long p,long q)
{list *c=new list;
c->x=p;
c->y=q;
c->urm=l;
l=c;}

long find(list *&l,long p)
{list *c;
for(c=l;c!=NULL;c=c->urm)
if(c->x==p)
       return c->y;
return -1001;}

void push(queue &q,long x)
{Nod *c=new Nod;
c->info=x;
c->next=NULL;
if(q.prim==NULL)
       q.prim=q.ultim=c;
else
       {q.ultim->next=c;
       q.ultim=c;}}
       
long pop(queue &q)
{long x=q.prim->info;
Nod *t=q.prim->next;
free(q.prim);
q.prim=t;
if(q.prim==NULL)
       q.ultim=NULL;
return x;}

int main()
{long n,m,i,j,k,c[N],d[N],co;
freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
queue q;
q.prim=q.ultim=NULL;
list *l[N];
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
      {c[i]=0;
      d[i]=1001;
      l[i]=NULL;}
for(k=1;k<=m;k++)
      {scanf("%ld%ld%ld",&i,&j,&co);
      add(l[i],j,co);}
d[1]=0;
push(q,1);
c[1]=1;
while(q.prim!=NULL)
      {i=pop(q);
      c[i]=1;
      for(j=1;j<=n;j++)
      if(find(l[i],j)!=-1001)
            {co=find(l[i],j);
            if(d[j]>d[i]+co)
                      {d[j]=d[i]+co;
                      if(c[j]==0)
                              {c[j]=1;
                              push(q,j);}}}}
for(i=2;i<=n;i++)
      printf("%ld ",d[i]);
fclose(stdin);
fclose(stdout);
return 0;}