#include <cstdio>
#define n_max 50000
#define m_max 250000
#include <vector>
#include <utility>
#define inf 1<<30
using namespace std;

struct lk{
 int x,cost;
};
int n, m;
vector <lk> grph[n_max];
int nxt[n_max], pos[n_max], d[n_max];

inline int father(int k){
    return k>>1;
}

inline int left_son(int k){
    return k<<1;
}

inline int right_son(int k){
    return ((k<<1)|1);
}

void sift(int k,int n){
   int son;
   do{
     son=0;
     if(left_son(k)<=n){
           son = left_son(k);
           if(right_son(k)<= n && d[nxt[son]]>d[nxt[right_son(k)]])
              son=right_son(k); 
       }
     if(d[nxt[son]]<d[nxt[k]]){
       pos[nxt[k]]=son;
       pos[nxt[son]]=k;
       swap(nxt[k],nxt[son]);
       k=son;
      }
   }while(son);
}

void percolate(int k, int n){
   
    while( k>1 && d[nxt[k]]>d[nxt[father(k)]]){
       pos[nxt[k]]=father(k);
       pos[nxt[father(k)]]=k;
       swap(nxt[father(k)],nxt[k]);
       k=father(k);
    }
} 

int main(void){
  freopen("dijkstra.in","r",stdin);
  int x,y,z;
  vector <lk> :: iterator it;
  lk aux;
  scanf("%d %d",&n, &m);
  while( m--){
     scanf("%d %d %d", &x, &y, &z);
     aux.x = y;
     aux.cost = z;
     grph[x].push_back(aux);     
   }
  int st=1,mn;
  for(int i=2;i <= n; ++i){
         pos[i]=-1;
         d[i]=inf;
      }
  pos[st]=1;
  nxt[st]=1;
  while(st){
     mn=nxt[1];
     swap(nxt[1],nxt[st]);
     pos[nxt[1]] = 1;
     st--;
     sift(1,st);
     for(it = grph[mn].begin();it != grph[mn].end(); ++it)
       if(d[it->x]>d[mn]+it->cost){
           d[it->x]=d[mn]+it->cost;
           if(pos[it->x]!=-1)percolate(pos[it->x],st);
           else {nxt[++st]=it->x;
                 pos[nxt[st]]=st;
                 percolate(st,st);
                }
        }
  }
  freopen("dijkstra.out","w", stdout);
  for(int i=2;i <= n; ++i)printf("%d ",d[i]==inf?0:d[i]);
}