#include <fstream>
using namespace std;
ifstream cin( "dijkstra.in" );
ofstream cout( "dijkstra.out" );

int n, m, d[ 50001 ];
struct edge { int x, y, c; };
edge array[ 250001 ];
int main()
{
	int i, ok;
	cin >> n >> m;
	for ( i = 1; i <= n; i++ )
		d[ i ] = 2000000000;
	for ( i = 1; i <= m; i++ )
	{
		cin >> array[ i ].x >> array[ i ].y >> array[ i ].c;
		if ( array[ i ].x == 1 )
			d[ array[ i ].y ] = array[ i ].c;
	}
	ok = 1;
	while ( ok )
	{
		ok = 0;
		for ( i = 1; i <= m; i++ )
			if ( d[ array[ i ].y ] > d[ array[ i ].x ] + array[ i ].c )
			{
				d[ array[ i ].y ] = d[ array[ i ].x ] + array[ i ].c;
				ok = 1;
			}
	}
	for ( i = 2; i <= n; i++ )
		cout << d[ i ] << " ";
}