#include<stdio.h>
#define INF 1 << 30
#define N 50005
FILE *f=fopen("dijkstra.in","r"), *g=fopen("dijkstra.out","w");

int d[N], H[N], el, n, m;
struct nod
{
	int y, c;
	nod *urm;
} *v[N];

void swap(int &a, int &b)
{
	a=a^b;
	b=a^b;
	a=a^b;
}
void downheap(int k)
{
	int son;
	do
	{
		son=0;
		if(k*2 <= el) son=k*2;
		if(k*2+1 <=el && d[ H [k*2+1] ] < d[ H[k*2] ])
			son= 2*k+1;
		if( d[H[k]] < d[H[son]])
			son=0;
		if(son)
			swap(H[k], H[son]);
		k=son;
	} while(son);
}

void upheap(int k)
{
	int val=d[ H[k] ];
	while(val < d[ H[ k/2 ]])
	{
		swap(H[k], H[k/2]);
		k=k/2;
	}
}
void push(int x)
{
	H[++el]=x;
	upheap(el);
}

void rez()
{
	int min;
	for(int i=1; i<=n;i++)
		d[i]= INF;
	for(nod *p=v[1]; p; p=p->urm)
	{
		d[ p->y ]= p->c;
		push(p->y);
	}
	
	for(int i=1; i<n;i++)
	{
		min=d[ H[1] ];
		for(nod *p=v[ H[1] ]; p; p=p->urm)
		{
			if( d[p->y] > p->c + min)
				if(d[p->y]==INF)
				{
					d[p->y]= p->c+min;
					H[++el]=p->y;
				}
				else 
				{
					d[p->y]= p->c+min;
					upheap(p->y);
				}
			
		}
		
		H[1]=H[el--];
		downheap(1);
	}
}

void add(int x, int y, int c)
{
	nod *p=new nod;
	p->c=c;
	p->y=y;
	p->urm=v[x];
	v[x]=p;
}

int main()
{
	int a, b, c;
	fscanf(f,"%d %d", &n, &m);
	for(int i=1;i<=m;i++)
	{
		fscanf(f,"%d %d %d", &a, &b, &c);
		add(a,b,c);
	}
	
	rez();
	
	for(int i=2;i<=n;i++)
		fprintf(g,"%d ", d[i]);
	return 0;
}