#include<stdio.h>
#include<stdlib.h>
#define INF 1002
long long N,M;
int **C;
void citire() {
	long long k,i,j;
	int cost;
	scanf("%d",&N);
	scanf("%d",&M);
	C=(int**)malloc((N+1)*sizeof(int*));
	for (k=0;k<=N;k++)
		C[k]=(int*)malloc((N+1)*sizeof(int));
	for(i=1;i<=N;i++)
		for(j=1;j<=N;j++)
		if(i==j) C[i][j]=0;
			else
				C[i][j]=INF;
	for(k=1;k<=M;k++){
		scanf("%d %d %d",&i,&j,&cost);
		C[i][j]=cost;
	}
}
void dijkstra (int x0) {
	long long i,minim,k,gata;
	long long viz[N+1],d[N+1],pred[N+1];
	for(i=1;i<=N;i++) {
			d[i]=C[x0][i];
			pred[i]=x0;
			viz[i]=0;
	}
	pred[x0]=0;
	viz[x0]= 1;
	gata=1;
	while(gata==1) {
		minim=INF;
		for(i=1;i<=N;i++)
			if(viz[i]==0 && minim >d[i]) {
				minim=d[i];
				k=i;
		}
		if (minim==INF)
					 gata=0;
		if(minim !=INF) {
			viz[k]=1;
			for(i=1;i<=N;i++)
				if(viz[i]==0 && d[i]>d[k]+C[k][i]) {
					d[i]=d[k]+C[k][i];
					pred[i]=k;
				}
		}
		}
		for(i=2;i<=N;i++)
			printf("%d",d[i]);
}
int main() {
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	citire();
	dijkstra(1);
	fclose(stdin);
	fclose(stdout);
	return 0;
}