#include<stdio.h>
#include<vector>
#define NMAX 5001
#define MMAX 250001
using namespace std;

int A[NMAX][NMAX];
int N, M;
int d[NMAX];

void read(FILE *pf){
	int i, j, a, b, c;
	fscanf(pf, "%d %d", &N, &M);	

	for(i = 1; i <= M; i++){
		fscanf(pf, "%d %d %d", &a, &b, &c);
		A[a][b] = c;
	}
}

void Dijkstra(){
	int i, k;
	for(i = 1; i <= N; i++){
		d[i] = A[1][i];
	}

	k = N;
	while(k > 1){
		for(i = 2; i <= N; i++)
			if(d[i] > d[k] + A[k][i] || d[i] == 0)
				if(d[k] && A[k][i])
					d[i] = d[k] + A[k][i];
		k--;
	}
}

void print(FILE *pg){
	int i;
	for(i = 2; i <= N; i++)
		fprintf(pg, "%d ", d[i]);
}

int main(){
	FILE *pf, *pg;
	pf = fopen("dijkstra.in", "r");
	pg = fopen("dijkstra.out", "w");

	read(pf);
	Dijkstra();
	print(pg);

	fclose(pf);
	fclose(pg);

	return 0;
}