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

int d[ 50001 ], dProb[ 50001 ], q[ 50001 ];
int x, y, cost, n, m, t, dMin, vMin, s, teste; 
vector<int> v[ 50001 ], c[ 50001 ];

int main()
{
	int i, j, ok;
		cin >> n >> m;
		for ( i = 1; i <= n; i++ )
			d[ i ] = 9999999;
		for ( i = 1; i <= m; i++ )
		{
			cin >> x >> y >> cost;
			if ( x == 1 )
				d[ y ] = cost;
			v[ x ].push_back( y );
			c[ x ].push_back( cost );
		}
		q[ 1 ]++;
		d[ 1 ] = 0;
		for ( j = 1; j < n; j++ )
		{
			dMin = 9999999;
			for ( i = 1; i <= n; i++ )
				if ( dMin > d[ i ] && q[ i ] < 1 )
				{
					dMin = d[ i ];
					vMin = i;
				}
			q[ vMin ]++;
			for ( i = 0; i < v[ vMin ].size(); i++ )
				if ( q[ v[ vMin ][ i ] ] < 1 && d[ v[ vMin ][ i ] ] > d[ vMin ] + c[ vMin ][ i ] )
					d[ v[ vMin ][ i ] ] = d[ vMin ] + c[ vMin ][ i ];
		}
		ok = 1;
		for ( i = 2; i <= n; i++ )
			if ( d[ i ] == 9999999 ) cout << "0 ";
			else cout << d[ i ] << " ";
}