#include <cstdio>

const int maxn = 50001;
const int inf = 1 << 30;

FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w");

struct graf
{
	int nod, cost;
	graf *next;
};

int n, m;
graf *a[maxn];
int d[maxn], h[maxn], poz[maxn], k;

void add(int where, int what, int cost)
{
	graf *q = new graf;
	q->nod = what;
	q->cost = cost;
	q->next = a[where];
	a[where] = q;
}

void read()
{
	fscanf(in, "%d %d", &n, &m);

	int x, y, z;
	for ( int i = 1; i <= m; ++i )
	{
		fscanf(in, "%d %d %d", &x, &y, &z);
		add(x, y, z);
	}
}

void swap(int x, int y)
{
	int t = h[x];
	h[x] = h[y];
	h[y] = t;
}

void upheap(int what)
{
	int tata;
	while ( what > 1 )
	{
		tata = what >> 1;

		if ( d[ h[tata] ] > d[ h[what] ] )
		{
			poz[ h[what] ] = tata;
			poz[ h[tata] ] = what;

			swap(tata, what);

			what = tata;
		}
		else
			what = 1;
	}
}

void downheap(int what)
{
	int f;
	while ( what <= k )
	{
		f = what;
		if ( (what<<1) <= k )
		{
			f = what << 1;
			if ( f + 1 <= k )
				if ( d[ h[f + 1] ] < d[ h[f] ] )
					++f;
		}
		else
			return;

		if ( d[ h[what] ] > d[ h[f] ] )
		{
			poz[ h[what] ] = f;
			poz[ h[f] ] = what;

			swap(what, f);

			what = f;
		}
		else
			return;
	}
}

void dijkstra_heap()
{
	for ( int i = 2; i <= n; ++i )
		d[i] = inf, poz[i] = -1;
	poz[1] = 1;

	h[++k] = 1;

	while ( k )
	{
		int min = h[1];
		swap(1, k);
		poz[ h[1] ] = 1;
		--k;

		downheap(1);

		graf *q = a[min];

		while ( q )
		{
			if ( d[q->nod] > d[min] + q->cost )
			{
				d[q->nod] = d[min] + q->cost;

				if ( poz[q->nod] != -1 )
					upheap( poz[q->nod] );
				else
				{
					h[++k] = q->nod;
					poz[ h[k] ] = k;
					upheap( k );
				}
			}
			q = q->next;
		}
	}
}

int main()
{
	read();
	dijkstra_heap();

	for ( int i = 2; i <= n; ++i )
		fprintf(out, "%d ", d[i] == inf ? 0 : d[i]);
	fprintf(out, "\n");

	return 0;
}