#include <vector>
#include <fstream>
#include <cstring>
#include <queue>
 
#define MAX_SIZE 50005
#define get_max( a,b) ((a)>(b)?(a):(b))
#define mk make_pair
#define INF 0x3f3f3f3f
 
using namespace std;

typedef vector < pair < int,int > > ::iterator vii;
 
ifstream in ( "dijkstra.in" );
ofstream out ( "dijkstra.out" );
 
vector <  pair < int  ,int > > G[MAX_SIZE] ;
int N , M , Cost[MAX_SIZE] ;
priority_queue < pair < int , int > , vector < pair < int , int > > , greater < pair < int , int > > > Heap;
 
void Dijkstra ( void )
{
	int i , j ; 
    for ( i = 1 ; i <= N ; Cost[i++] = INF);
	Cost[1] = 0 ;
    Heap.push(mk( 1 , 0));
    for ( ; !Heap.empty() ; )
    {
        int node = Heap.top().first , val = Heap.top().second;
        Heap.pop();
      for( i = 0 ; i <G[node].size(); ++i )
      {
       int newnode=G[node][i].first;
       int dis=G[node][i].second;
       if( Cost[newnode] > Cost[node]+dis)
          {
              Cost[newnode]=Cost[node]+dis;
              Heap.push(mk( newnode , Cost[newnode] ) );
          }
  
	  } 
	}	  
}
 
 
int main ( void )
{
    int i , j , x , y , c ;
    in >> N >> M ;
    for ( i = 1 ; i <= M ; ++i )
    {
        in >> x >> y >> c ;
        G[x].push_back(mk(y,c));
    }
    Dijkstra();
    for ( i = 2 ; i <= N ; ++i )
        out << ( Cost[i] == INF ? 0 : Cost[i] ) << " ";
    in.close();
    out.close();
    return 0 ;
}