#include<stdio.h>
#define nmax 50005
struct nod
 {
  int bog,cost;
  nod *next;
 };
nod *a[nmax];
int heap[nmax],pos[nmax],L,N,M,d[nmax];
const int inf= 1 << 30;
void add (int x,int y,int z)
 {
  nod *q=new nod;
  q->bog=y;
  q->cost=z;
  q->next=a[x];
  a[x]=q;
 }

void push (int x)
 {
  int aux,y=0;
  while (y!=x)
   {
    y=x;
    if (y*2<=L && d[heap[x]]>d[heap[y*2]])
      x=y*2;
    if (y*2+1<=L && d[heap[x]]>d[heap[y*2+1]])
      x=y*2+1;
    aux=heap[x];
    heap[x]=heap[y];
    heap[y]=aux;
    pos[heap[x]]=x;
    pos[heap[y]]=y;
   }
 }

void pull (int x)
 {
  int aux;
  while (x/2 && d[heap[x]]<d[heap[x/2]])
   {
    aux=heap[x];
    heap[x]=heap[x/2];
    heap[x/2]=aux;
    pos[heap[x]]=x;
    pos[heap[x/2]]=x/2;
    x>>=1;
   }
 }

void dijkstra()
 {
  int i;
  for (i=2;i<=N;++i)
    d[i]=inf,pos[i]=-1;
  heap[++L]=1;
  pos[heap[1]]=1;
  int min;
  while (L)
   {
    min=heap[1];
    heap[1]=heap[L--];
    pos[heap[1]]=1;
    push(1);
    nod *q=a[min];
    while (q)
     {
      if (d[q->bog] > d[min] + q->cost)
       {
	d[q->bog]=d[min]+q->cost;
	if (pos[q->bog]!=-1)
	  pull (pos[q->bog]);
	else
	 {
	  heap[++L]=q->bog;
	  pos[heap[L]]=L;
	  pull (L);
	 }
       }
      q=q->next;
     }
   }
  }
int main()
 {
  freopen("dijkstra.in","r",stdin);
  freopen("dijkstra.out","w",stdout);
  scanf("%d%d",&N,&M);
  int i,x,y,z;
  for (i=1;i<=M;++i)
   {
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z);
   }
  dijkstra();
  for (i=2;i<=N;++i)
   if (d[i]!=inf)
    printf("%d ",d[i]);
   else
    printf("0 ");
  return 0;
 }