#include <cstdio> 
const int maxn = 50001; 
const int inf = 1 << 30; 
FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w"); 
struct graf 
{ 
   
int nod, cost;    
graf *next; 
}; 
int n, m; 
graf *a[maxn]; 
int d[maxn], h[maxn], poz[maxn], k; 
void add(int where, int what, int cost) 
{   
graf *q = new graf;     
q->nod = what;     
q->cost = cost;     
q->next = a[where];     
a[where] = q; 
} 
void read() 
{     
fscanf(in, "%d %d", &n, &m);   
int x, y, z;     
for ( int i = 1; i <= m; ++i )     
{        
fscanf(in, "%d %d %d", &x, &y, &z);         
add(x, y, z);     
} 
} 

void swap(int x, int y) 
{ 
int t = h[x];     
h[x] = h[y]; 
h[y] = t; 
} 

void upheap(int what) 
{ 
int tata;    
while ( what > 1 )     
{ 
        
tata = what >> 1; 
    
if ( d[ h[tata] ] > d[ h[what] ] )       
{             
poz[ h[what] ] = tata;             
poz[ h[tata] ] = what;          
swap(tata, what); 
      
what = tata;         
}         
else            
what = 1;     
} 
} 

void downheap(int what) 
{    
int f; 
   
while ( what <= k )     
{         
f = what;         
if ( (what<<1) <= k )        
{             
f = what << 1;            
if ( f + 1 <= k )                 
if ( d[ h[f + 1] ] < d[ h[f] ] )                     
++f;        
}         
else            
return; 
        
if ( d[ h[what] ] > d[ h[f] ] )         
{             
poz[ h[what] ] = f;            
poz[ h[f] ] = what; 
swap(what, f); 
what = f;        
}         
else            
return;     
} 
} 
void dijkstra_heap() 
{    
for ( int i = 2; i <= n; ++i )         
d[i] = inf, poz[i] = -1;    
poz[1] = 1;  
h[++k] = 1;    
while ( k )     
{         
int min = h[1];         
swap(1, k);        
poz[ h[1] ] = 1;        
--k;        
downheap(1); 
graf *q = a[min];        
while ( q )        
{            
if ( d[q->nod] > d[min] + q->cost )            
{                 
d[q->nod] = d[min] + q->cost;           
if ( poz[q->nod] != -1 )                     
upheap( poz[q->nod] );                 
else                
{                     
h[++k] = q->nod;                     
poz[ h[k] ] = k;                  
upheap( k );                 
}            
}             
q = q->next;         
}     
} 
} 
int main() 
{    
read();  
dijkstra_heap();    
for ( int i = 2; i <= n; ++i )         
fprintf(out, "%d ", d[i] == inf ? 0 : d[i]);     
fprintf(out, "\n");    
return 0; 
}