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

struct nod
{
	int j, c;
	nod *urm;
} *v[N]; 

void add(int a, int b, int c)
{
	nod*p =new nod;
	p->j=b;
	p->c=c;
	p->urm=v[a];
	v[a]=p;
}

void rez()
{
	int min, poz;
	
	for(int i=1;i<=n;i++)
		d[i]=inf;
	
	for(nod*p=v[1]; p; p=p->urm)
		d[p->j]=p->c;
			
	s[1]=true;
	
	for(int i=1;i<n;i++)
	{
		min=inf;	
		for(int i=1;i<=n;i++)
			if(d[i]<min && !s[i])
			{
				poz=i;
				min=d[i];
			}
		
		s[poz]=true;
		for(nod *p = v[poz]; p ; p=p->urm)
			if( d[p->j]> min+p->c )
				d[p->j]=min+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;
}