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

int n, m, lg, uz[NMax], dx[NMax];
struct muchie{ int x, y, cost; } heap[NMax];
std::vector<muchie> a[NMax];

void citire();
void rez();

// heap
void upHeap( int x );
void downHeap( int x );
void push( muchie x );
void swap( muchie &a, muchie &b );
int getL( int x );
int getR( int x );
int getP( int x );
muchie pop();

int main()
{
	citire();
	rez();
	return 0;
}
void rez()
{
	int i, j, lgx;
	muchie aux;

	lgx = a[1].size();

	for (i=2; i<=n; i++)
		dx[i] = INF;

	for (i=0; i<lgx; i++)
	{
		push( a[1][i] );
		dx[a[1][i].y] = a[1][i].cost;
	}

	uz[1] = 1;

	for (i=1; i<n; i++)
	{
		aux = pop();

		uz[aux.y] = 1;
		lgx = a[aux.y].size();

		for (j=0; j<lgx; j++)
			if ( !uz[a[aux.y][j].y] && dx[a[aux.y][j].y] > dx[aux.y] + a[aux.y][j].cost )
			{
				dx[a[aux.y][j].y] = dx[aux.y] + a[aux.y][j].cost;
				push( a[aux.y][j] );
			}
	}

	for (i=2; i<=n; i++)
		printf( "%d ", dx[i] );
}
void citire()
{
	int i;
	muchie x;

	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.x, &x.y, &x.cost );
		a[x.x].push_back(x);
	}
}
// heap
void upHeap( int x )
{
	int p;

	if ( x==1 )
		return;

	p = getP( x );

	if ( heap[p].cost > heap[x].cost )
		swap( heap[p], heap[x] );

	upHeap(p);
}
void downHeap( int x )
{
	int c1, c2, sel;

	if ( x * 2 > lg )
		return;

	c1 = getL( x );
	c2 = getR( x );

	sel = (heap[c1].cost<heap[c2].cost)?c1:c2;

	if ( heap[sel].cost < heap[x].cost )
		swap( heap[sel], heap[x] );

	downHeap(sel);
}
void push( muchie x )
{
	heap[++lg] = x;
	upHeap( lg );
}
void swap( muchie &a, muchie &b )
{
	muchie c;
	c = a;
	a = b;
	b = c;
}
int getL( int x )
{ return x*2; }
int getR( int x )
{ return x*2+1; }
int getP( int x )
{ return x/2; }
muchie pop()
{
	muchie aux;

	aux     = heap[1];
	heap[1] = heap[lg--];
	downHeap(1);

	return aux;
}