#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct ListNode
{
    unsigned int neighbour,cost;
    struct ListNode *next;
} AdjList;

void AddToList(AdjList **head,unsigned int neighbour,unsigned int cost)
{
    if(NULL==(*head))
    {
        (*head)=(AdjList *)malloc(sizeof(AdjList));
        (*head)->neighbour=neighbour;
        (*head)->cost=cost;
        (*head)->next=NULL;
        return;
    }

    AdjList *temp=(AdjList *)malloc(sizeof(AdjList));
    temp->neighbour=neighbour;
    temp->cost=cost;
    temp->next=(*head);
    (*head)=temp;
}
void PurgeList(AdjList **head)
{
    if(NULL==(*head))
    {
        (*head)=NULL;
        free(*head);
        return;
    }

    AdjList *temp=(*head);
    (*head)=(*head)->next;
    temp=NULL;
    free(temp);

    PurgeList(head);
}
void swap(unsigned int *a,unsigned int *b)
{
    unsigned int aux=(*a);
    (*a)=(*b);
    (*b)=aux;
}
void UpHeap(unsigned int *heap,unsigned int *dist,unsigned int *posInHeap,unsigned int curr_pos,unsigned int len)
{
   unsigned int next_pos;

   while(curr_pos>1)
   {
       next_pos=(curr_pos>>1);

       if(dist[heap[next_pos]]<dist[heap[curr_pos]]){

          posInHeap[heap[curr_pos]]=next_pos;
          posInHeap[heap[next_pos]]=curr_pos;

          swap(&heap[curr_pos],&heap[next_pos]);
       }

       curr_pos=next_pos;
   }
}
void Downheap(unsigned int *heap,unsigned int *dist,unsigned *posInHeap,unsigned int curr_pos,unsigned int len)
{

    unsigned int next_pos;

    while(curr_pos<=len){

        next_pos=curr_pos;
        if((curr_pos<<1)<=len){

            next_pos=(curr_pos<<1);
            if(next_pos+1<=len && dist[heap[next_pos+1]]<dist[heap[next_pos]])
                next_pos+=1;
        }
        else return;

        if(dist[heap[curr_pos]]>dist[heap[next_pos]]){

             posInHeap[heap[curr_pos]]=next_pos;
             posInHeap[heap[next_pos]]=curr_pos;

             swap(&heap[next_pos],&heap[curr_pos]);

             curr_pos=next_pos;
        }
        else return;
    }

}
void Dijkstra(AdjList **list,unsigned int *heap,unsigned int len,int *dist,unsigned int *posInHeap,unsigned int start,unsigned int n)
{

   for(unsigned int i=1;i<=n;i++)
   {
       dist[i]=(1<<30);
       posInHeap[i]=-1;
   }

   dist[1]=0;
   posInHeap[1]=1;
   len++;
   heap[len]=1;

   while(len>0)
   {
      int min=heap[1];
     swap(&heap[1],&heap[len]);
      posInHeap[heap[1]]=1;
      len--;

      Downheap(heap,dist,posInHeap,1,len);

      AdjList *L=list[min];

      while(NULL!=L)
      {
          if(dist[L->neighbour]>dist[min]+L->cost){

            dist[L->neighbour]=dist[min]+L->cost;

            if(posInHeap[L->neighbour]!=-1)
               UpHeap(heap,dist,posInHeap,posInHeap[L->neighbour],len);
            else{
                heap[++len]=L->neighbour;
                posInHeap[heap[len]]=len;
                UpHeap(heap,dist,posInHeap,len,len);
            }
          }
          L=L->next;
      }
   }
}
int main()
{

    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    unsigned int n,m,a,b,c,len=0;
    scanf("%u %u",&n,&m);

    AdjList **list=(AdjList **)malloc(sizeof(AdjList*)*(n+1));

    for(unsigned int i=0; i<=n; i++)
        list[i]=NULL;

    unsigned int *heap=(unsigned int *)malloc(sizeof(unsigned int)*(n+1));
    int *posInHeap=(int *)calloc(n+1,sizeof(int));
    unsigned int *dist=(unsigned int *)calloc(n+1,sizeof(unsigned int));

    for(unsigned int i=0; i<m; i++)
    {
        scanf("%u %u %u",&a,&b,&c);
        AddToList(&list[a],b,c);
    }

    Dijkstra(list,heap,len,dist,posInHeap,1,n);

    for(unsigned int i=2;i<=n;i++)
        printf("%u ",(dist[i]==(1<<30) ? 0:dist[i]));

    for(unsigned int i=0; i<=n; i++)
        PurgeList(&list[i]);
    free(list);

    free(heap);
    free(dist);
    free(posInHeap);

    return 0;
}