#include <stdio.h>
#include <stdlib.h>
#define N 50005
#define INF 2000000000
int n,m,*a[N],*b[N],v[2*N],d[N];
bool f[N];
void solve(){
	int i,j;
	for(i=1;i<=n;i++)
		d[i]=INF;
	d[1]=0;
	v[++v[0]]=1;
	for(i=1;i<=v[0];i++){
		f[v[i]]=false;
		for(j=1;j<=a[v[i]][0];j++)
			if(d[a[v[i]][j]]>d[v[i]]+b[v[i]][j]){
				d[a[v[i]][j]]=d[v[i]]+b[v[i]][j];
				if(!f[a[v[i]][j]]){
					v[++v[0]]=a[v[i]][j];
					f[a[v[i]][j]]=true;
				}
			}
	}
	for(i=2;i<=n;i++)
		printf("%d ",d[i] == INF? 0:d[i]);
}
int main(){
	int i,x,y,z;
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		a[i]=(int*)malloc(4);
		b[i]=(int*)malloc(4);a[i][0]=b[i][0]=0;
	}
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		a[x][0]=++b[x][0];
		if(a[x][0]%16==1) {
			a[x]=(int*)realloc(a[x], (a[x][0]+16)*4);
			b[x]=(int*)realloc(b[x], (b[x][0]+16)*4);
		}
		a[x][a[x][0]]=y; b[x][b[x][0]]=z;
	}
	solve();
	return 0;
}