#include <stdio.h>
#include <vector>
#define NMax 50000
#define INF 32000

// prog stuff
int n, m;
std::vector<int> vecini[NMax];
std::vector<int> cost[NMax];

void citire();
void afis();

// heap stuff
int heap[NMax], lg;
int getLeft( int x );
int getRight( int x );
int getParent( int x );
int pop();
void addNode( int x );
void delNode( int x );
void goUp( int x );
void goDown( int x );

// Dijkstra stuff
int dmin[NMax];
void dijkstra();
int getCost( int vf, int vf2 );


int main()
{
	citire();
	dijkstra();
	afis();
	return 0;
}
// dijkstra stuff
void dijkstra()
{
	int i, j, lg, vfmin, cst, d, aux, uz[NMax];

	for (i=1; i<=n; i++)
		uz[i] = -1;

	uz[1] = 1;
	lg    = vecini[1].size();

	for (i=0; i<=n; i++)
		dmin[i] = INF;

	for (i=0; i<lg; i++)
	{
		dmin[vecini[1][i]] = cost[1][i];
		addNode( vecini[1][i] );
	}

	for (i=1; i<n; i++)
	{
   		vfmin = pop();
		lg = vecini[vfmin].size();

 		uz[vfmin] = 1;
		for (j=0; j<lg; j++)
		{
			cst = getCost(vfmin, vecini[vfmin][j]);
			if ( uz[vecini[vfmin][j]] == -1 && dmin[vecini[vfmin][j]] > dmin[vfmin] + cst )
			{
				dmin[vecini[vfmin][j]] = dmin[vfmin] + cst;
				addNode( vecini[vfmin][j] );
			}
		}
	}
}
int getCost( int vf, int vf2 )
{
	int i, lg;

	lg = vecini[vf].size();
	for (i=0; i<lg; i++)
		if ( vecini[vf][i] == vf2 )
			return cost[vf][i];
}

// prog stuff
void afis()
{
	int i;

	for (i=2; i<=n; i++)
		printf( "%d ", dmin[i] );
	printf( "\n" );
}
void citire()
{
	int i, x, y, z;
	freopen( "dijkstra.in", "rt", stdin );
	freopen( "dijkstra.out", "wt", stdout );

	scanf( "%d %d", &n, &m );
	for (i=0; i<m; i++)
	{
		scanf( "%d %d %d", &x, &y, &z );

		vecini[x].push_back(y);
		cost[x].push_back(z);
	}
}
// heap stuff
int getLeft( int x )
{ return 2*x; }
int getRight( int x )
{ return 2*x+1; }
int getParent( int x )
{ return x/2; }
int pop()
{
	int aux;

	aux = heap[1];
	delNode( 1 );

	return aux;
}
void goUp( int x )
{
	if ( x == 1 )
		return;

	int aux, par = getParent(x);

	if ( dmin[heap[par]] > dmin[heap[x]] )
	{
		aux       = heap[x];
		heap[x]   = heap[par];
		heap[par] = aux;
	}
	goUp( par );
}
void goDown( int x )
{
	int aux, c1, c2, dir;

	if ( x >= lg )
		return;
	
	c1 = getLeft( x );
	c2 = getRight( x );

	dir = c1;
	if ( dmin[heap[c1]] > dmin[heap[c2]] )
		dir = c2;
	
	aux      = heap[x];
	heap[x]  = heap[dir];
	heap[dir] = aux;

	goDown( dir );
}
void delNode( int x )
{
	heap[x]  = heap[lg];
	heap[lg] = 0;
	lg--;

	goDown( x );
	
}
void addNode( int x )
{
	heap[++lg] = x;
	goUp( lg );
}