#include <stdio.h>
#include <string.h>
#include <queue>
#define oo 0x3f3f3f3f
#define dim 50010
using namespace std;
 
int n, m, x, y, viz[ dim ], best[ dim ];
queue < int > Q;

struct graf
{
	int nod, cost;
	graf *next;	
};
graf *a[ dim ], *q;

void citire()
{	
	int x, y, z;
	FILE *f = fopen( "dijkstra.in", "r" );		
	
	fscanf( f, "%d %d", &n, &m ); 
	
    for ( int i = 1; i <= m; ++i )
    {
        fscanf( f, "%d %d %d", &x, &y, &z);
		graf *q = new graf;
		q->nod = y;
		q->cost = z;
		q->next = a[x];
		a[ x ] = q;
    }
	fclose(f);
}

void dijkstra()
{
	memset ( best, oo, sizeof( best ) );
	best[ 1 ] = 0;
	Q.push( 1 ); 
	q = a[ 1 ];
        
    while ( !Q.empty() )
    {
        x = Q.front();
        Q.pop();
        viz[ x ] = 0;
        q = a[ x ];
		
		while ( q )
		{
    		y = q->nod;
			
            if ( best[ y ] > best[ x ] + q->cost )
            {
                best[ y ] = best[ x ] + q->cost;        
                
                if ( !viz[ y ] ) 
				{
					Q.push( y );
					viz[ y ] = 1;
				}
            }
			q = q->next;
        }   
    }
}

void afisare()
{
	FILE *g = fopen( "dijkstra.out", "w" );
  
	for ( int i = 2; i <= n; ++i )
        if ( best[ i ] == oo )
            fprintf( g,"0 " );
        else fprintf( g,"%d ", best[ i ] );
		
    fprintf( g,"\n" );    
	fclose( g );
}

int main()
{
	citire();
	dijkstra();
	afisare();
	
return 0;
}