#include<fstream>
#include<algorithm>
using namespace std;

typedef struct lnod {
        int info,cost;
        lnod *next;
}*nod;

typedef struct lol {
        int nod,cost;
}troll;

int i,n,m,x,y,z,nr,d[50005];
nod lda[50005];
troll heap[200005];
bool viz[50005];

void add(int x,nod &y,int z) {
     nod p=new lnod;
     p->info=x;
     p->cost=z;
     p->next=y;
     y=p;
}

void upheap() {
     int aux=nr;
     while(aux>1 && heap[aux/2].cost>heap[aux].cost)
     swap(heap[aux],heap[aux/2]),aux/=2;
}

void downheap() {
     heap[1]=heap[nr--];

     int nod=1;
     while(2*nod<=nr)
     {
       int index=nod;
       if(heap[2*nod].cost<heap[index].cost) index=2*nod;
       if(2*nod<nr && heap[2*nod+1].cost<heap[index].cost) index=2*nod+1;

       if(index==nod) break;
       else swap(heap[nod],heap[index]),nod=index;
     }
}

int main()
{
  ifstream cin("dijkstra.in");
  ofstream cout("dijkstra.out");

  cin>>n>>m;
  while(m--) cin>>x>>y>>z,add(y,lda[x],z);

  heap[++nr].nod=1;
  upheap();

  while(nr)
  {
    x=heap[1].nod;
    downheap();
    if(!viz[x]) {
                  viz[x]=1;
                  for(nod p=lda[x];p;p=p->next)
                  if(!d[p->info] || d[p->info]>d[x]+p->cost)
                  d[p->info]=d[x]+p->cost,heap[++nr].nod=p->info,
                  heap[nr].cost=d[p->info],upheap();
                }
  }

  for(i=2;i<=n;++i) cout<<d[i]<<' ';

 return 0;
}