#include <cstdio>
#define n_max 50010
#define m_max 250010
#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;
   while(k<=n){
      if(left_son(k) <= n){
         son=left_son(k);
         if(right_son(k)<=n && d[nxt[right_son(k)]]<d[nxt[son]])son=right_son(k);
       }
      else break;
      if(d[nxt[son]]<d[nxt[k]]){
          pos[nxt[k]]=son;
          pos[nxt[son]]=k;
          swap(nxt[k],nxt[son]);
       }
      else break;
    }
}

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

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]);
}