#include<cstdio>
#include<list>
#include<complex>
#include<cstdlib>
#include<queue>

#define FILE_IN   "dijkstra.in"
#define FILE_OUT  "dijkstra.out"

#define NMAX 250000
#define INF 2*1000*1000*1000

using namespace std;

int N, M, *Cost, *Parent;
list< pair<int,int> > E[ NMAX ];

void read();
void dijkstra( int );
void write();
void clean();

int main(){
  
  read();
  dijkstra( 1 );
  write();
  clean();
  
}

void clean(){
  free( Cost );
  free( Parent );
}

void write(){
  freopen( FILE_OUT, "w", stdout );
  for( int i=2; i<=N; ++i ){
    printf( "%d ", Cost[i] );
  }
}

void dijkstra( int start ){
  list< pair<int,int> >::iterator it;
  queue<int> q;
  
  q.push( start );
  Cost[ start ] = 0;
  
  while( !q.empty() ){
    int p = q.front();
    q.pop();
    for( it=E[p].begin(); it!=E[p].end(); ++it ){
      if( Cost[p] + (*it).second < Cost[ (*it).first ] ){
        Cost[ (*it).first ]   = Cost[p] + (*it).second;
        Parent[ (*it).first ] = p;
      }
      q.push( (*it).first );
    }
  }
}

void read(){
  freopen( FILE_IN, "r", stdin );
  scanf( "%d %d", &N, &M );
  
  Cost    = (int *) malloc( (N+1) * sizeof( int ) );
  Parent  = (int *) malloc( (N+1) * sizeof( int ) );
  
  for( int i=0; i<=N; ++i ){
    Cost[i]   = INF;
    Parent[i] = 0;
  }
  
  for( int i=0; i<M; ++i ){
    int a,b,c;
    scanf("%d %d %d", &a, &b, &c );
    E[a].push_back( make_pair( b,c ) );
  }
}