#include <cstdio>
#include <string>
#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, y, c;};

nod a[250001];
int d[50001];
int n, m;

void read()
{
	freopen("dijkstra.in","r",stdin);
	cit(n);cit(m);
	for(int i=1;i<=m;++i) cit(a[i].x), cit(a[i].y), cit(a[i].c);
	
}

void bell()
{
	int ok=1,i;
	int p,q,c;
	memset(d, oo, sizeof(d));
	d[1]=0;
	
	while(ok)
	{
		ok=0;
		for(i=1;i<=m;++i)
		{
			p=a[i].x, q=a[i].y, c=a[i].c;
			if(d[p] + c < d[q]) d[q]=d[p]+c, ok=1;
		}
	}
	
	for(i=2;i<=n;++i)
		if(d[i]==oo) printf("0 ");
				else printf("%d ", d[i]);
		
	
}

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