# include <stdio.h>

# define input "dijkstra.in"
# define output "dijkstra.out"

# define max 50003
# define INF 16000

int n,m,i,x,y,c,sh,j;
int d[max],h[max],pos[max];

struct lista
{
	int nod,cost;
	lista * urm;
}*g[max];

void adauga(int x,int y,int c)
{
	lista * f = new lista;
	f->nod = y;
	f->cost = c;
	f->urm = g[x];
	g[x] = f;
}
void swap(int st,int dr)
{
	pos[h[st]] = dr;
	pos[h[dr]] = st;

	int aux = h[st];
	h[st] = h[dr];
	h[dr] = aux;
}
void heapup(int x)
{
	while(x>1)
	{
		if(d[h[x]] < d[h[x>>1]])
		{
			swap(x,x>>1);
			x>>=1;
		}
		else
			break;
	}
}
void heapdown()
{
	h[1] = h[sh];
	h[sh] = n+1;
	sh--;
	int x = 1;
	while(2*x<=sh)
	{
		int pos = 2*x;
		if(pos+1 <= sh)
			if(d[h[pos]] > d[h[pos+1]])
				pos++;
		if(d[h[x]] > d[h[pos]])
			swap(x,pos);
		else
			break;
		x = pos;
	}
}

void dijkstra()
{
	while(sh)
	{
		j = h[1];
//		printf("%d ",j);
		heapdown();
		for(lista * f = g[j];f;f=f->urm)
		{
			if(d[f->nod] > d[j] + f->cost)
			{
				d[f->nod] = d[j] + f->cost;
				heapup(pos[f->nod]);
			}
		}
	}
}

int main()
{
	freopen(input, "r", stdin);
	freopen(output, "w", stdout);

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

	for(i=1;i<=m;i++)
	{
		d[i] = INF;
		pos[i] = h[i] = n+1;
		scanf("%d%d%d",&x,&y,&c);
		adauga(x,y,c);
	}


	lista * f = g[1];

	while(f)
	{
		d[f->nod] = f->cost;
		f=f->urm;
	}

	for(i=2;i<=n;i++)
	{
		h[++sh] = i;
		pos[i] = sh;
		heapup(sh);
	}

	dijkstra();

//    printf("\n");

	for(i=2;i<=n;i++)
        if(d[i]==INF)
        printf("0 ");
        else
		printf("%d ",d[i]);
	return 0;
}