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

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

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

int n,m,x,y,z,nr,i,d[50005];
bool viz[50005];
troll h[250005];
nod lda[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 nod=nr;
     while(nr>1 && h[nod/2].cost>h[nod].cost)
     swap(h[nod],h[nod/2]),nod/=2;
}

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

       if(index==nod) break;
       else swap(h[nod],h[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);

  h[++nr].nod=1;

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

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

 return 0;
}