#include <iostream>
using namespace std;
const int maxn = 50001;
const int inf = 1 << 30;
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 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()
{

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

return 0;
}