#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],h[MaxN], poz[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 swap(int &x, int &y){
	int aux;
	aux = x;
	x = y;
	y = aux;
};

inline int father(int x){
	return x/2;
}
inline int l_son(int x){
	return 2*x;
};
inline int r_son(int x){
	return 2*x + 1;
};

void down_heap(int x){
	int y;
	y = poz[x];
	while (y > 1 && (d[ h[ father(y) ] ] > d[ h[y] ])){
		swap(poz[ h[father(y)] ], poz[ h[y] ]);
		swap(h[ father(y) ], h[y]);
		y /= 2; //aici se poate optimiza, in caz ca nu intra in timp	un singur swap

	}
	if (y > 1 && d[ h[ (y/2)*2] ] > d[ h [ (y/2)*2 + 1]]){
		swap(poz[h [(y/2)*2] ], poz[h[(y/2)*2 +1 ] ]);
		swap(h[(y/2)*2],h[(y/2)*2 +1 ]);
	}
};

void up_heap(int x){
	int fiu,y;
	y = poz[x];
	do{
		fiu = 0;
		if ( l_son(y) <= h[0]){
			fiu = l_son(y);
		
			if (r_son(y) <= h[0] && d[ h[ r_son(y) ] ] <= d[ h[ l_son(y) ] ] )
				fiu = r_son(y);
			if ( d[ h[ fiu ] ] >= d[ h[ y ] ] )
				fiu = 0;
		}
		if (fiu){
			swap(poz[ h[y] ], poz[ h[fiu] ]);
			swap(h[ y ], h[fiu]);
		}
	}
	while (fiu);	
	
};
void dijkstra(){
	int min, min_ind;
	min_ind = 1;
	h[0] = n-1;
	for (int i = 2; i <= n; ++ i)
		d[i] = MaxVal;
	for (int i = 1; i <= n-1; ++ i)
		h[i] = i+1, poz[i+1] = i;
	d[0] = -1;
	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, down_heap(p->info);
	
	viz[min_ind] = true;
	h[1] = h[ h[0] ]; 
	poz[h[1]] = 1;
	h[ h[0] ] = 0;
	--h[0];

	if (h[0] != 0)up_heap(h[1]);
	min_ind = h[1];

	}while (h[0] != 0 && d[h[1]] != MaxVal);	

}

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;
};