//Dijkstra pe heap
#include <cstdio>
#include <string>
#define DIM 8192
#define N 50001
#define oo 0x3f3f3f3f
#define L ((i)<<1)
#define R ((L)+1)
#define T ((i)>>1)

char ax[DIM];
int  pz;

inline void cit(int &x)
{
	x=0;
	while(ax[pz]<'0' || ax[pz]>'9')
		if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
	
	while(ax[pz]>='0' && ax[pz]<='9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
	}
}

struct nod { int x, cost;nod *n;};

nod *a[N];
int n, m, d[N], H[N], poz[N], nh;

void read()
{
	
	cit(n);cit(m);

	int p, q, c;
	while(m--)
	{
		cit(p);cit(q);cit(c);
		nod *t=new nod;
		t->x=q;
		t->cost=c;
		t->n=a[p];
		a[p]=t;
	}
}

inline void swap(int i, int j)
{
	int t=H[i]; H[i]=H[j]; H[j]=t;
	poz[H[i]]=i;
	poz[H[j]]=j;
}

inline void upheap(int i)
{
	if(i<=1) return;
	if(d[H[T]] > d[H[i]]) swap(i, T), upheap(T);
}

inline void downheap(int i)
{
	int m=i;
	
	if(L<=nh)
		if(d[H[m]] > d[H[L]]) m=L;
	if(R<=nh)
		if(d[H[m]] > d[H[R]]) m=R;
	
	if(m!=i) swap(m,i), downheap(m);
}



void dijkstra()
{
	
	memset(d, oo, sizeof(d));
	d[1]=0;
	
	int i;
	for(i=1;i<=n;++i) H[i]=i, poz[i]=i;
	
	for(i=n/2; i; --i) downheap(i); //creare heap O(n)
	
	nh=n;
	
	int u;
	nod *it;
	
	while(nh)
	{
		u=H[1];
		swap(1, nh--);
		downheap(1);
		
		for(it=a[u]; it; it=it->n)
			if(d[u] + it->cost < d[it->x])
			{
				d[it->x]=d[u] + it->cost;
				upheap(poz[it->x]);
			}
	}
	
	for(i=1;i<=n;++i) if(d[i]==oo) d[i]=0;
	for(i=2;i<=n;++i) printf("%d ", d[i]);
	
	
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	dijkstra();
	return 0;
}