#include <stdio.h>

#define pinf 1000000000

int d[1005],s[1005],t[1005],a[1005][1005],n,m,min,poz;

void daicstra ( int r ){
	s[r]=1;
	for(int i=1; i<=n; ++i)
		d[i]=a[r][i];
	for(int i=2; i<=n; ++i)
		if( (a[r][i]!=0) && (a[r][i]<pinf) )
			t[i]=r;
	for( int aiurea=0; aiurea<n; aiurea++){
		min=pinf;
		for(int i=1; i<=n; ++i)
			if( (!s[i]) && d[i]<min){
				min=d[i];
				poz=i;
			}
		s[poz]=1;
		for(int j=1; j<=n; ++j)
			if(d[j]>d[poz]+a[poz][j]){
				d[j]=d[poz]+a[poz][j];
				t[j]=poz;
			}
	}
}

void afisare_domne( int nod ){
	for(int i=2; i<=n; ++i)
		if(d[i]==pinf)
			printf("0 ");
		else
			printf("%d ",d[i]);
	printf("\n");
}

int main(){
	
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	int x,y;
	
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(i==j)
				a[i][j]=0;
			else
				a[i][j]=pinf;
	
	for (int i=1; i<=m ; ++i){
		scanf("%d%d",&x,&y);
		scanf("%d",&a[x][y]);
	}
	
	/*for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j)
			printf("%d ",a[i][j]);
		printf("\n");
	}
	*/
	daicstra(1);
	
	afisare_domne (1);
	
	return 0;
}