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

int n, m, x, y, c, d[ 50001 ], inf, minim;
int poz[ 50001 ], heap[ 50001 ], k;
struct graf
{
	int nod, cost;
	graf *next;
}*a[ 50001 ], *q;

void swap( int x,int y )
{
	int aux;
	aux = heap[ x ];
	heap[ x ] = heap[ y ];
	heap[ y ] = aux;
}

void upheap( int nod )
{
	int t;
	while ( nod > 1 )
	{
		t = nod / 2;
		if ( d[ heap[ t ] ] > d[ heap[ nod ] ] )
		{
			poz[ heap[ t ] ] = nod;
			poz[ heap[ nod ] ] = t;
			swap( t,nod );
			nod = t;
		}
		else nod = 1;
	}
}

void downheap( int nod )
{
	int f;
	while ( nod <= k )
	{
		f = nod * 2;
		if ( f <= k )
			if ( f + 1 <= k )
			{
				if ( d[ heap[ f ] ] > d[ heap[ f + 1 ] ] )
					f++;
			}
		else return;
		if ( d[ heap[ f ] ] > d[ heap[ nod ] ] )
		{
			poz[ heap[ f ] ] = nod;
			poz[ heap[ nod ] ] = f;
			swap( f,nod );
			nod = f;
		}
		else return;
	}
}

int main()
{
	int i, j;
	cin >> n >> m;
	for ( i = 1; i <= m; i++ )
	{
		cin >> x >> y >> c;
		q = new graf;
		q->nod = y;
		q->cost = c;
		q->next = a[ x ];
		a[ x ] = q;
	}
	inf = 2000000000;
	for ( i = 2; i <= n; i++ )
		d[ i ] = inf;
	poz[ 1 ] = 1;
	heap[ ++k ] = 1;
	while ( k )
	{
		minim = heap[ 1 ];
		swap( 1,k );
		poz[ heap[ 1 ] ] = 1;
		k--;
		downheap( 1 );
		q = a[ minim ];
		while ( q )
		{
			if ( d[ q->nod ] > d[ minim ] + q->cost )
			{
				d[ q->nod ] = d[ minim ] + q->cost;
				if ( poz[ q->nod ] )
					upheap( poz[ q->nod ] );
				else
				{
					heap[ ++k ] = q->nod;
					poz[ q->nod ] = k;
					upheap( k );
				}
			}
			q = q->next;
		}
	}
	for ( i = 2; i <= n; i++ )
		if ( d[ i ] < inf ) cout << d[ i ] << " ";
		else cout << "0 ";
}