#include <fstream>
using namespace std;
ifstream f ("dijkstra.in");
ofstream g ("dijkstra.out");
struct point {int x,c; point *y;} *G[50001];
int m,n,i,j,k,x,y,c,nod,h[50001],d[50001],t[50001],p[50001];
inline void intro(int x, int y, int c)
{   point *q=new point;
	q->x=y; q->c=c; q->y=G[x]; G[x]=q;
}
inline void swap(int i, int j)
{   int x;
	x=h[i]; h[i]=h[j]; h[j]=x;
	x=p[h[i]]; p[h[i]]=p[h[j]]; p[h[j]]=x;
}
void heapup(int i)
{   if(d[h[i/2]]<d[h[i]]) return;
	swap(i,i/2); heapup(i/2);
}
void heapdown(int i)
{   if(i*2>m) return;
    int dr,st=d[h[i*2]];
	if(i*2+1<=m) dr=d[h[i*2+1]]; else dr=st+1;
	if(st<dr)
	{   if(d[h[i]]<=st) return;
		swap(i,2*i); heapdown(i*2);
	}
	else
	{   if(d[h[i]]<=dr) return;
		swap(i,2*i+1); heapdown(2*i+1);
	}
}
int main()
{
	f >> n >> m;
	for(i=0;i<m;i++) {f >> x >> y >> c; intro(x,y,c);}
	for(i=1;i<=n;i++) {d[i]=2000000000; h[i]=i; p[i]=i;}
	m=n;
	d[1]=0;
	d[0]=-1;
	for(i=0;i<n;i++)
	{   nod=h[1];
		swap(1,m);
		m--;
		heapdown(1);
		for(point *q=G[nod];q!=NULL;q=q->y)
			if(d[q->x]>d[nod]+q->c)
			{   d[q->x]=d[nod]+q->c;
				t[q->x]=nod;
				heapup(p[q->x]);
			}
	}
	for(i=2;i<=n;i++)
		if(d[i]==2000000000) g << "0 "; else g << d[i] << ' ';
	return 0;
}