#include <fstream>
#define MaxN 50001
#define MaxVal 60000000
using namespace std;
fstream FIN ("dijkstra.in", ios::in);
fstream FOUT("dijkstra.out", ios::out);

int n,m;
bool viz[MaxN], mod;
int d[MaxN], q[MaxN];
struct vert {
	int info, cost;
	vert *next;
} *L[MaxN];

void add(int ex1, int ex2, int c){

	vert *p = new vert;
	p->info = ex2;
	p->cost = c;
	p->next = L[ex1];
	L[ex1] = p;

};

void read(){

	FIN>>n>>m;
	
	int ex1,ex2,c;
	for (int i = 1; i <= m; ++ i){
		FIN>>ex1 >>ex2 >>c;
		add(ex1,ex2,c);
	}
}

void dijkstra(){
	int min, min_ind;
	min_ind = 1;
	
	for (int i = 2; i <= n; ++ i)
		d[i] = MaxVal;
	do {
	for (vert *p = L[min_ind]; p != NULL; p = p->next)
		if (! viz[p->info])
			if (d[min_ind] + p->cost < d[p->info])
				d[p->info] = d[min_ind] + p->cost;
	viz[min_ind] = true;
	min = MaxVal + 1;
	mod = false;
	for (int i = 2; i <= n; i++)
		if (! viz[i] )
			if (d[i] < min)
				min = d[i], min_ind = i, mod = true;
	}
	while (mod);	

}

void print(){

	for (int i = 2; i <= n; i++)
		if (d[i] == MaxVal) FOUT<<"0 ";
		else FOUT<<d[i]<<" ";
}

int main(){

	read();
	dijkstra();
	print();

return 0;
};