# include <fstream>
# include <algorithm>
# include <vector>
# include <queue>

# define dim 50002
# define inf 99999

# define pb push_back


using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct pereche
{
	int nod, cost;
};

int n, m;

vector <pereche> a[ dim ];
vector <int> drum( dim , inf );

queue <int> q;

void citire()
{
 int i, j, x, y, c;
 f >> n >> m ;
 
 for ( i = 1 ; i <= m ; i++ )
	{
		f >> x >> y >> c;
		a[ x ].pb( ( pereche ) { y, c } );
	}
}

void dijkstra()
{
	int i, x, xx;
	x = 1;
	drum[ x ] = 0;
	q.push( x );
	
	while ( !q.empty () )
	{
		xx = q.front();
		for ( i = 0 ; i < a[ xx ].size() ; i++ )
			if ( drum[ xx ] + a[ xx ][ i ].cost < drum[ a[ xx ][ i ].nod ] )
			{
				drum[ a[ xx ][ i ].nod ] = drum[ xx ] + a[ xx ][ i ].cost;
				q.push( a[ xx ][ i ].nod );
			}
			q.pop();
	}	
}

void afisare()
{
	int i, j;
	/*
	for ( i = 1 ; i <= n ; i++ )
	{
		for ( j = 0 ; j < a[ i ].size() ; j++ )
			g << a[ i ][ j ].nod << " ";
		g << "\n";
	}
	g << "\n";
	for ( i = 1 ; i <= n ; i++ )
	{
		for ( j = 0 ; j < a[ i ].size() ; j++ )
			g << a[ i ][ j ].cost << " ";
		g << "\n";
	}
	g << "\n" ;
	*/
	for ( i = 2 ; i <= n ; i++ )
		if ( drum[ i ] == inf )
			g << 0 << " ";
		else
			g << drum[ i ] << " ";
	
}

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