#include <stdio.h>
#include <fstream.h>

# define inf 0x3f3f3f3f
# define MAX 50010
typedef struct nod {
			int key,c;
			nod *next;
		   };

int m, n, nh=0, d[MAX], viz[MAX],heap[2*MAX];
nod *a[MAX];
void add ( int x,int y, int cost )
{
 nod * p;
	p = new nod;
	p->key = y;
	p->c = cost;
	p->next = a[x];
	a[x] = p;

}

void cit ()
{
 int x,y,c;

//	freopen ( "dijkstra.in", "r", stdin );

//	scanf ( "%d %d", &n, &m );
ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");
fin>>n>>m;
	for ( int i = 0; i < m; i++ )
		{
			//scanf ( "%d %d %d", &x, &y, &c );
			fin>>x>>y>>c;
			add(x,y,c); d[y] = inf;d[x]=inf;
		}
//fclose ( stdin );
}

void minheap(int nod) //mentine proprietatea de min heap
{
	int st=2*nod, dr=2*nod+1, max = 0, aux;
	if (st<=nh && d[heap[st]] < d[heap[nod]])
		max=st;
	if (dr<=nh && d[heap[dr]] < d[heap[nod]] && d[heap[dr]]<=d[heap[st]])
		max=dr;
	if (max != 0 )
	{
		aux=heap[nod];
		heap[nod] = heap[max];
		heap[max] = aux;
		minheap(max);
	}
}

void push ( int v ) //insereaza elementul v in heap
{
	int aux;
	heap[++nh] = v;
	for (int i=nh; i>1; i= i>>1 )
		if (d[heap[i >> 1]] > d[heap[i]])
		{
		aux=heap[i >> 1];
		heap[i >> 1] = heap[i];
		heap[i] = aux;
		}
}

int pop () // scoate elementul minim din heap
{
	int rez = heap[1];
	heap[1] = heap[nh--];
	minheap(1);
	return rez;
}

void init ()
{
	int vertex = 1;
	viz[1] = 1;
	for ( nod *p = a[vertex]; p; p=p->next )
		 {
			d[p->key] = p->c;
			push ( p->key );
		 }
	for ( int i = 2; i <=n; ++ i )
		if ( d[i] == inf )
			push ( i );
}


void inbunatatire_drum ( int vf )
{
 for ( nod *p = a[vf]; p; p= p->next )
		if ( d[p->key] > d[vf] + p->c )
		 {
			d[p->key] = d[vf] + p->c;
			push ( p->key );
		 }
}

void djikstra ()
{
 int min;

	while ( nh >= 0 )
	 {
		min = pop ();
		viz[min] = 1;
		inbunatatire_drum(min);
	 }

}

void afish ()
{
	freopen ( "dijkstra.out", "w", stdout );
	for ( int i = 2; i<= n; i++ )
		if ( d[i] != inf )
			printf ( "%d ", d[i] );
		else
			printf ( "0 " );
	fclose ( stdout );
}

int main ()
{
	cit ();
	init();
	djikstra();
	afish();
	return 0;
}