#include<stdio.h>
#define MaxVal 250000100
struct Nod {
    int val;
    int cost;
    Nod *next;
};
struct NodInHeap {
    int val;
    int PozInGraf;
};
int n;
int dimHeap;
int m;
int PozInHeap[100005];
int x;
int z;
int y;
Nod *a[100005];
int aux2;
NodInHeap Heap[200009];
NodInHeap aux;

int insert(Nod *&u, int V,int C)
{
    Nod *k = new Nod;
    k -> val = V;
    k -> cost = C;
    k -> next = u;
    u = k;
}
void Up(int nod)
{

         NodInHeap aux;
         while (Heap[nod].val < Heap[nod / 2].val && nod > 1)
          {
              aux = Heap[nod];
              Heap[nod] = Heap[nod / 2];
              Heap[nod / 2] = aux;
              aux2 = PozInHeap[Heap[nod].PozInGraf];
              PozInHeap[Heap[nod].PozInGraf] = PozInHeap[Heap[nod / 2].PozInGraf];
              PozInHeap[Heap[nod / 2].PozInGraf] = aux2;
              nod /= 2;
          }

}
void Heapify(int nod)
{
    int min = nod;
    NodInHeap aux;
    if (dimHeap >= 2 * nod + 1)
    if (Heap[2 * nod].val < Heap[2 * nod + 1].val) min = 2 * nod;
                                              else min = 2 * nod + 1;
        else
    if (dimHeap >= 2 * nod)
      min = 2 * nod;
     if (Heap[min].val >= Heap[nod].val) min = nod;
    if (min != nod)
     {
         aux = Heap[nod];
         Heap[nod] = Heap[min];
         Heap[min] = aux;
         aux2 = PozInHeap[Heap[nod].PozInGraf];
         PozInHeap[Heap[nod].PozInGraf] = PozInHeap[Heap[min].PozInGraf];
         PozInHeap[Heap[min].PozInGraf] = aux2;
         Heapify(min);
     }

}
NodInHeap ExtractMin()
{
    NodInHeap aux;
    aux = Heap[1];
    Heap[1] = Heap[dimHeap];
    Heap[dimHeap] = aux;
    /*aux2 = PozInHeap[Heap[1].PozInGraf];
    PozInHeap[Heap[1].PozInGraf] = PozInHeap[Heap[dimHeap].PozInGraf];
    PozInHeap[Heap[dimHeap].PozInGraf] = aux2;*/
    PozInHeap[Heap[1].PozInGraf] = 1;
    PozInHeap[Heap[dimHeap].PozInGraf] = dimHeap;
    dimHeap--;
    Heapify(1);
    return Heap[dimHeap + 1];
}

void Dijkstra(int s)
{
    for(int i = 1; i <= n; i++)
    {
     PozInHeap[i] = Heap[i].PozInGraf = i;
     Heap[i].val = MaxVal;
    }
    Heap[1].val = 0;
    while (dimHeap)
     {
         aux = ExtractMin();
         for(Nod *it = a[aux.PozInGraf]; it; it = it -> next)
          if (Heap[PozInHeap[it -> val]].val > aux.val + it -> cost)
           {
           Heap[PozInHeap[it -> val]].val = aux.val + it -> cost;
           Up(PozInHeap[it->val]);
           }
     }
}

int main()
{
    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,&z);
         insert(a[x],y,z);
     }
    dimHeap = n;
     Dijkstra(1);
    for(int i = 2; i <= n; i++)
     printf("%d ",Heap[PozInHeap[i]].val);
}