#include <cstdio>
#include <string>
#define N 50001
#define oo 0x3f3f3f3f
#define DIM 8192 

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;
int d[N];

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;
	}
}

void bellman()
{
	memset(d, oo, sizeof(d));
	d[1]=0;
	
	int Q[(1<<16)+13], p=0,q=0;
	bool inq[N];
	memset(inq, 0, sizeof(inq));
	const int mod=(1<<16)-1;
	int nr=1;//nr elemente din coada
	Q[0]=1;
	inq[1]=1;
	int u;
	nod *it;
	
	while(nr)
	{
		u=Q[p++];
		p&=mod;
		--nr;
		inq[u]=0;
		
		for(it=a[u]; it; it=it->n)
			if(d[u] + it->cost < d[it->x])
			{
				d[it->x]=d[u] + it->cost;
				if(!inq[it->x])
				{
					
					++q; q&=mod;
					Q[q]=it->x;
					++nr;
				}
			}
	}

	for(int i=2;i<=n;++i) printf("%d ", d[i]);
	
}


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