#include <stdio.h>

typedef struct {
	int a, b, c;
} Edge;

int n,j;
int e; 
Edge edges[250000]; 
int d[50000]; 

#define INFINITY 1000000

void printDist() {
	int i;
	for (i = 1; i < n; ++i)
		printf("%d ",d[i]);
	printf("\n");
}
void bellman_ford(int s) {
	int i, j;

	for (i = 0; i < n; ++i)
		d[i] = INFINITY;

	d[s] = 0;

	for (i = 0; i < n - 1; ++i)
		for (j = 0; j < e; ++j)
			if (d[edges[j].a] + edges[j].c < d[edges[j].b])
				d[edges[j].b] = d[edges[j].a] + edges[j].c;
}
int main () {
	int i;
	int w=0;
	int a,b,c;
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	scanf("%d", &n);
	scanf("%d",&e);
	for(i=0;i<e;++i){
		scanf("%d%d%d",&a,&b,&c);
		edges[w].a=a-1;
		edges[w].b=b-1;
		edges[w].c=c;
		++w;
	}
	bellman_ford(0);
	printDist();
	return 0;
}