#include <cstdio>
#define fius( x ) ( x ) * 2
#define fiud( x ) ( x ) * 2 + 1
#define tata( x ) ( x ) / 2
#define MAX 500001
#include<vector>
#define INF 1<<30

using namespace std;

int heap[MAX],poz[MAX],dim,M,N,v[MAX];
vector < pair< int, int > > muchii[MAX];

void schimba(int x,int y)
 {int aux=heap[x];
  heap[x]=heap[y];
  heap[y]=aux;  }

void up_heap(int nod)
{
 while(nod>1 && v[heap[nod]]<v[heap[tata(nod)]])
 { poz[heap[nod]]=tata(nod);
   poz[heap[tata(nod)]]=nod;
   schimba(nod,tata(nod));
   nod=tata(nod);
 }
}

void down_heap(int nod)
{ while((fius(nod)<=dim && v[heap[fius(nod)]]<v[heap[nod]])||(fiud(nod)<=dim && v[heap[fiud(nod)]]<v[heap[nod]]))
   if(fiud(nod)<=dim)
    {
     if(v[heap[fius(nod)]]<v[heap[fiud(nod)]])
       { schimba(nod,fius(nod));
         poz[heap[nod]]=nod;
         poz[heap[fius(nod)]]=fius(nod);
         nod=fius(nod);
        }
    else
     { schimba(nod,fiud(nod));
       poz[heap[nod]]=nod;
       poz[heap[fiud(nod)]]=fiud(nod);
       nod=fiud(nod);
     }
   }
  else
  { schimba(nod,fius(nod));
    poz[heap[nod]]=nod;
    poz[heap[fius(nod)]]=fius(nod);
    nod=fius(nod);
  }
}

void dijkstra()
{int min,cost,nod;
 for(int i=2;i<=N;++i)
  {
   poz[i]=-1; v[i]=INF;
  }
 heap[++dim]=1;
 poz[1]=1;
 while(dim)
  { min=heap[1];
    schimba(1,dim);
    poz[heap[1]]=1;
    dim--;
    down_heap(1);
    for(int j=0;j<muchii[min].size();++j)
     {
       nod=muchii[min][j].first;
       cost=muchii[min][j].second;
        if (cost+v[min]<v[nod])
         {
           v[nod]=cost+v[min];
           if (poz[nod]!=-1)
             up_heap(poz[nod]);
           else
           { heap[++dim]=nod;
             poz[nod]=dim;
             up_heap(dim);}
             }
        }

     }
}

int main()
{  int x,y,c;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;++i)
    {   scanf("%d%d%d",&x,&y,&c);
        muchii[x].push_back( make_pair(y,c));
    }
  dijkstra();

  for(int i=2;i<=N;++i)
   if (v[i] != INF)
      printf("%d ",v[i]);
    else
    printf("0 ");
return 0;
}