#include<stdio.h>

struct Nod {
   int d,cost;
   Nod *urm;
};
struct NodHeap  {
   int v;
   int cost;
};
Nod *a[50002];
NodHeap Heap[100000];
int pozheap[50002];
int dist[50002];
int i,s,d,cost,op2,op,n,m,dimheap;
int insert(Nod *&k,int op,int op2)
{
  Nod *x = new Nod;
  x->d=op;
  x->cost=op2;
  x->urm=k;
  k=x;
}
int intrschmb(NodHeap &t1,NodHeap &t2)
{
   NodHeap aux;
   int aux2;
   aux=t1;
   aux2=pozheap[t1.v];
   pozheap[t1.v]=pozheap[t2.v];
   t1=t2;
   pozheap[t2.v]=aux2;
   t2=aux;
   return 0;
}
int Heapify(int source)
{
   int val=source;
   if (2*source+1<=dimheap)
   if (Heap[2*source].cost<Heap[2*source+1].cost) val=2*source;
                                             else val=2*source+1;
   else
    if (2*source<=dimheap) val=2*source;
   if (Heap[val].cost<Heap[source].cost)
       {
       intrschmb(Heap[val],Heap[source]);
       Heapify(val);
       }
   return 0;
}
NodHeap ExtractMin()
{
    NodHeap aux;
    aux=Heap[1];
    intrschmb(Heap[1],Heap[dimheap]);
    dimheap--;
    Heapify(1);
    return aux;
}
int Update(int poz1,int cst)
{
   Heap[poz1].cost=cst;
   while (Heap[poz1].cost<Heap[poz1/2].cost&&poz1!=1)
     {
     intrschmb(Heap[poz1],Heap[poz1/2]);
     poz1/=2;
     }
  return 0;
}
int BuildHeap(int aux)
{
    dimheap++;
    pozheap[aux]=dimheap;
    Heap[dimheap].v=aux;
    Heap[dimheap].cost=1000000000;
    Update(pozheap[aux],Heap[dimheap].cost);
}
int Dijkstra(int source)
{
  NodHeap aux;
  Nod *i;
  int j;
  for(j=1;j<=n;j++)
   BuildHeap(j);
  Update(pozheap[source],0);
  while(dimheap)
   {
      aux=ExtractMin();
      dist[aux.v]=aux.cost;
      for(i=a[aux.v];i!=NULL;i=i->urm)
        if (aux.cost+i->cost<Heap[pozheap[i->d]].cost)
          Update(pozheap[i->d],aux.cost+i->cost);
   }
}
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",&s,&d,&cost);
    insert(a[s],d,cost);
   }
  Dijkstra(1);
  for(i=2;i<=n;i++)
  {
   if (dist[i]!=1000000000) printf("%ld ",dist[i]);
                        else printf("0 ");
  }
  printf("\n");
  return 0;
}