#include<stdio.h>
#include<queue>
#define NMAX 50001
#define MMAX 250001
#define INF NMAX*NMAX
using namespace std;

struct AdListElem{
	int node;
	int cost;
	AdListElem *next;
};

int N, M, d[NMAX], v[NMAX];
struct AdListElem *L[NMAX];
queue<int> Q;

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

	for(i = 1; i <= M; i++){
		fscanf(pf, "%d %d %d", &a, &b, &c);
		p = new AdListElem;
		p->node = b;
		p->cost = c;
		p->next = L[a];
		L[a] = p;
	}
}

void Dijkstra(){
	int i, a, b;
	struct AdListElem *p;
	for(i = 1; i <= N; i++){
		d[i] = 0;
		v[i] = 0;
	}
	
	Q.push(1);
	while(!Q.empty()){
		a = Q.front();
		Q.pop();
		p = L[a];
		v[a] = 0;
		while(p != NULL){
			b = p->node;
			if(d[b] > d[a] + p->cost || d[b] == 0){
				d[b] = d[a] + p->cost;
				if(v[b] == 0){
					Q.push(b);
					v[b] = 1;
				}
			}
			p = p->next;
		}
	}		
}

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

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

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

	fclose(pf);
	fclose(pg);

	return 0;
}