#include<stdio.h>
#include<stdlib.h>
#define NMAX 50003
#define inf (1<<30)
#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
using namespace std;

struct graf{int nod,cost;graf * urm;} *g[NMAX];
int h[NMAX],d[NMAX],k,poz[NMAX],n,m,a,b,c;

void swap(int x,int y)
 {int aux;
  aux=h[x];
  h[x]=h[y];
  h[y]=aux;
     
     }

void up(int x)
 {int tata;
  while(x>1)
   {tata=x>>1;
    if(d[h[tata]]>d[h[x]])
     {poz[h[tata]]=x;
      poz[h[x]]=tata;
      swap(tata,x);
      x=tata;
      }
    else x=1;         
             }
     }
     
void down(int x)
{int fiu;
 while(x<=k)
  {fiu=x;
  if((x<<1) <=k)
   {fiu=x<<1;
   if(fiu+1 <= k)
     if(d[h[fiu+1]]<d[h[fiu]])
     fiu++;
          }   
    else return;
   if(d[h[x]]>d[h[fiu]])
    {poz[h[x]]=fiu;
    poz[h[fiu]]=x;
     swap(x,fiu);                   
     x=fiu;}
    else return;          
            }
     
     }  
     
void dijkstra()
{for(int i=1;i<=n;i++)
 {d[i]=inf;poz[i]=-1;}
 poz[1]=1;
 d[1]=0;
 h[++k]=1;
 while(k)
 {int x=h[1];
  
  swap(1,k);
  poz[h[1]]=1;
  k--;
  down(1);
  for(graf *i=g[x];i;i=i->urm) 
   {if(d[i->nod]>d[x]+i->cost)
    {d[i->nod]=d[x]+i->cost;
    if(poz[i->nod]!=-1)
      up(poz[i->nod]);
    else{h[++k]=i->nod;
    poz[h[k]]=k;
    up(k); }}
           }       
         }    
     
     } 
int main()
{
    freopen(FIN,"r",stdin);
    freopen(FOUT,"w",stdout);
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;i++)
     {scanf("%d %d %d",&a,&b,&c);
      graf *q=new graf;
      q->nod=b;
      q->cost=c;
      q->urm=g[a];
      g[a]=q;
             }
     dijkstra();
     for(int i=2;i<=n;i++)
      if(d[i]==inf) printf("0 ");
      else printf("%d ",d[i]);
      return 0;        
    
    }