#include<stdio.h>
#define N 50001
#define inf 1<<30
FILE *f=fopen("dijkstra.in","r"), *g=fopen("dijkstra.out","w");
int n,m;
short s[N];
long long d[N];

struct nod
{
	int i,j,c;
	nod *urm;
} *prim, *ult, *p; 

void add(int a, int b, int c)
{
	nod*p =new nod;
	p->i=a;
	p->j=b;
	p->c=c;
	p->urm=NULL;
	if(!prim)
		prim=ult=p;
	else
	{
		ult->urm=p;
		ult=p;
	}
}

void rez()
{
	for(int i=2;i<=n;i++)
		d[i]=inf;
	d[1]=0;
	
	for(int i=1;i<=n;i++)
	{
		for(nod*p=prim; p; p=p->urm)
			if(d[p->i]!=inf)
				if(d[p->j]> d[p->i]+ p->c)
					d[p->j]=d[p->i]+ p->c;
	}	
}
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=1;i<=n;i++)
		if(d[i]<inf) 
			fprintf(g,"%lld ", d[i]);
		else fprintf(g,"0 ");
	return 0;
}