#include<stdio.h>
#define MAX 50001
int n,m,d[MAX],s[MAX],p[MAX],X,L[3][300002],nrelem,order[MAX],ind,cont;
struct bla
{
	int val,order;
}heap[MAX],aux;
int right_son(int x)
{
	return x*2 + 1;
}
int left_son(int x)
{
	return x*2;
}
int father(int x)
{
	return x/2;
}
void sift(int x)
{
	int son;
	do
	{
		son = 0;
		if(left_son(x) <= nrelem)
		{
			son = left_son(x);
			if(right_son(x) <= nrelem && heap[son].val > heap[right_son(x)].val)
				son = right_son(x);
		}
		if(heap[son].val >= heap[x].val)
			son = 0;
		
		if(son)
		{
			order[heap[son].order] = x;
			order[heap[x].order] = son;
			aux = heap[son];
			heap[son] = heap[x];
			heap[x] = aux;
			x = son;
		}
	}while(son);
}
void percolate(int x)
{
	while(heap[father(x)].val > heap[x].val && father(x))
	{
		order[heap[father(x)].order] = x;
		order[heap[x].order] = father(x);
		
		aux = heap[father(x)];
		heap[father(x)] = heap[x];
		heap[x] = aux;
		x = father(x);
	}
}
void insert(int x)
{
	heap[++nrelem].val = x;
	heap[nrelem].order = ind+1;
	order[++ind] = nrelem;
	percolate(nrelem);
}
void cut(int x)
{
	heap[x] = heap[nrelem--];
	sift(x);
	if(heap[father(x)].val > heap[x].val && father(x))
		percolate(x);
}
void update(int x,int val)
{
	heap[x].val = val;
	sift(x);
	if(heap[father(x)].val > heap[x].val && father(x))
		percolate(x);
}
void init()
{
	int i;
	for(i=1;i<=n;++i)
	{
		d[i] = 999999;
		order[i] = i;
		heap[i].order = i;
		heap[i].val = 999999;
	}
	cont = n+1;
	nrelem = n;
	X = 1;
	s[X] = 1;
	cut(order[X]);
}
void add(int x,int y,int c)
{
	if(!L[1][x])
	{
		L[1][x] = cont;
	}
	else
	{
		L[1][L[0][x]] = cont;
	}
	L[0][x] = cont;
	L[0][cont] = y;
	L[2][cont] = c;
	++cont;
}
int detmin()
{
	int i,min = 999999,p = 0;
	for(i=1;i<=n;++i)
		if(d[i]<min && !s[i]){p = i;min = d[i];}
	return p;
}
void make(int min)
{
	int var = L[1][min],j;
	while(var)
	{
		j = L[0][var];
		if(L[2][var] + d[min] < d[j])
		{
			d[j] = L[2][var] + d[min];
			update(order[j],d[j]);
			p[j] = min;
		}
		var = L[1][var];
	}
}
int main()
{
	FILE*f = fopen("dijkstra.in","r");
	fscanf(f,"%d %d",&n,&m);
	init();
	int x,y,c,i;
	for(i=1;i<=m;++i)
	{
		fscanf(f,"%d%d%d",&x,&y,&c);
		if(x == X)
		{
			d[y] = c;
			update(order[y],c);			
			p[y] = x;
		}
		else add(x,y,c);
	}
	fclose(f);
	d[X] = 0;
	
	int nr = 1;
	while(nr<=n)
	{
		i = heap[1].order;
		cut(1);
		s[i] = 1;
		
		make(i);		
		++nr;
	}
	
	FILE*g = fopen("dijkstra.out","w");
	for(i=2;i<=n;++i)
	{
		if(d[i] == 999999){fprintf(g,"0 ");continue;}
		fprintf(g,"%d ",d[i]);
	}
	fclose(g);
	return 0;
}