#include<fstream>
#include<iostream>
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
#define infinit 1000000000
struct nod{
	int y,ct;
	nod* next;
};

nod *l[500001];
int d[500001],n,m,s[500001];

void add(int x,int y,int ct){
	nod *n=new(nod);
	n->y=y;
	n->ct=ct;
	n->next=l[x];
	l[x]=n;
}



void citire(){
	in>>n>>m;
	int x,y,ct;
		for(int i=1;i<=m;i++){
		in>>x>>y>>ct;
		add(x,y,ct);
		
	}
}

void dijkstra(int r){
nod *nc=l[r];
int min=infinit,poz;
while(nc){
	d[nc->y]=nc->ct;
	if(min>nc->ct) {min=nc->ct;
	poz=nc->y;
	}
	nc=nc->next;
}
	
	s[r]=1;
	for(int j=1;j<n;j++){ 
		min=infinit;
			for(int i=1;i<=n;i++)
			if(d[i]!=0&&!s[i])
				if(d[i]<min){
					poz=i;
					min=d[i];
				}
			s[poz]=1;
			nc=l[poz];
			while(nc){
					int sc=d[poz]+nc->ct;
					if(!s[nc->y]&&(sc<d[nc->y]||d[nc->y]==0))
						d[nc->y]=sc;
					nc=nc->next;
						
				}
		}
	
}

int main(){
	citire();
	int r=1;
	dijkstra(r);
	for(int i=2;i<=n;i++)
		out<<d[i]<<" ";
	
	out<<"\n";
	return 0;
}