#include <stdio.h>
#define NMax 100
#define INF 32000

int n, m, lg;
int v[NMax][NMax], cost[NMax][NMax], d[NMax];
struct vf{ int x, cost; } heap[NMax];

void citire();
void dijkstra();
void afis();

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

int main()
{
	citire();
	dijkstra();
	afis();
	return 0;
}
void citire()
{
	int i, j, x, y, z;

	freopen( "dijkstra.in", "rt", stdin );
	freopen( "dijkstra.out", "wt", stdout );

	scanf( "%d %d", &n, &m );

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

	for (i=0; i<m; i++)
	{
		scanf( "%d %d %d", &x, &y, &z );
		v[x][++v[x][0]] = y;
		cost[x][y] = z;
	}
}
void dijkstra()
{
	int i, j, aux, uz[NMax];
	vf x;

 	for (i=1; i<=n; i++)
	{
		uz[i] = 0;
		d[i]  = cost[1][i];

		x.x = i;
		x.cost = cost[1][i];

		if ( cost[1][i] != INF && i != 1 )
			push( x );
	}

	uz[1] = 1;
	d[1]  = 0;

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

		uz[aux] = 1;

		for (j=1; j<=v[aux][0]; j++)
			if ( !uz[v[aux][j]] && d[v[aux][j]] > d[aux] + cost[aux][v[aux][j]] )
			{
				d[v[aux][j]] = d[aux] + cost[aux][v[aux][j]];

				x.x    = v[aux][j];
				x.cost = d[aux] + cost[aux][v[aux][j]];
				push( x );
			}
	}
}
void afis()
{
	int i;

	for (i=2; i<=n; i++)
		printf( "%d ", d[i] );
}

int pop()
{
	int aux = heap[1].x;

	heap[1] = heap[lg--];
	downHeap(1);
	
	return aux;
}
int getL( int x )
{ return x*2; }
int getR( int x )
{ return x*2+1; }
int getP( int x )
{ return x/2; }
void swap( vf &a, vf &b )
{
	vf aux;

	aux = a;
	a   = b;
	b   = aux;
}
void push( vf x )
{
	heap[++lg] = x;
	upHeap( lg );
}
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 );
}