#include<cstdio>
#include<cstdlib>

#define NMAX 50000
#define MMAX 250 000
const int inf=1<<30;

int n,m;

int v[NMAX];

int c[10000][10000];

void cit()
{
	scanf("%d%d",&n,&m);
	
	int i,j;
	
	for(i=1; i<=n; i++)
		for(j=1; j<=n; j++)
			c[i][j]=10001;
	
	for(i=1; i<=m; i++)
	{
		int x,y,p;
		scanf("%d%d%d",&x,&y,&p);
		c[x][y]=p;
	}
}

void initializare()
{
	
	for(int i=2; i<=n; i++)
		v[i]=inf;
	
	v[1]=0;
	
}

void dijkstra()
{
	int i,j;
	for(i=1; i<=n; i++)
		for(j=2; j<=n; j++)
			if(v[j]>v[i]+c[i][j])
				v[j]=v[i]+c[i][j];
			
	for(i=2; i<=n; i++)
		if(v[i]==inf)
			v[i]=0;
}
	
void afis()
{
	for(int i=2; i<=n; i++)
		printf("%d ",v[i]);
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	cit();
	initializare();
	
	dijkstra();
	afis();
}