//#include<algorithm>
//using namespace std;
#include<stdio.h>

//#define DIM 50001
//#define INF 1000001

#define DIM 50001
#define INF 2000001

struct djk{
	int d,f,poz;};

struct graf{
	int nod,cost;
	graf *urm;};

int n,m,cnt,h[DIM];
djk a[DIM];
graf *lst[DIM];

inline int fath(int k){

	return k>>1;}

inline int lson(int k){

	return k<<1;}

inline int rson(int k){

	return k<<1+1;}

void add(int a,int b,int c){
    graf *p=new graf;

    p->nod=b;
    p->cost=c;
    p->urm=lst[a];
    lst[a]=p;}

void swap(int a,int b){
	int aux;

	aux=h[a];
	h[a]=h[b];
	h[b]=aux;}

int uph(int k){
	int poz;

	for(poz=h[k]; k>1&&a[h[k]].d<a[h[fath(k)]].d; k=fath(k))
		h[k]=h[fath(k)];
	h[k]=poz;
	return k;}

void downh(int k){
	int poz,son;

	poz=h[k];
	do{
		son=0;
		if(lson(k)<=cnt){
			son=lson(k);
			if(rson(k)<=cnt&&a[h[rson(k)]].d<a[h[lson(k)]].d)
				son=rson(k);
			if(a[h[son]].d>=a[h[k]].d)
				son=0;}
		if(son){
			h[k]=h[son];
			k=son;}}
	while(son);
	h[k]=poz;}

void upd(int k){

	if(k>1&&a[h[k]].d<a[h[fath(k)]].d)
		uph(k);
	else
		downh(k);}

int insert(int poz){

	h[++cnt]=poz;
	return uph(cnt);}

void cut(int k){

	h[k]=h[cnt--];
	upd(k);}

void init(){
	int i;

	for(i=2; i<=n; ++i)
		a[i].d=INF;}

void dijkstra(){
	int i;
	graf *p;

	h[++cnt]=1;
	for(i=1; i<=n; ++i){
		a[h[1]].f=1;
		for(p=lst[h[1]]; p; p=p->urm)
			if(a[h[1]].d+p->cost<a[p->nod].d){
				a[p->nod].d=a[h[1]].d+p->cost;
				if(!a[p->nod].poz)
					a[p->nod].poz=insert(p->nod);
				else
					upd(a[p->nod].poz);}
		cut(1);}}

void solve(){
	int i,x,y,z;

	scanf("%d%d",&n,&m);
	for(i=0; i<m; ++i){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);}
	init();
	/*dijkstra();*/}

void print(){
	int i;

	for(i=2; i<=n; ++i){
		if(a[i].d==INF)
			a[i].d=0;
		printf("%d ",a[i].d);}}

int main(){

	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);

	solve();
	print();
	return 0;}