#include<fstream.h>
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

struct nod{
	int y,ct;
	nod*next;
};

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

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;
	for(int i=1;i<=m;i++){
		int x,y,ct;
		in>>x>>y>>ct;
		add(l[x],y,ct);
	}
}

void dijkstra(int r){
	nod*nc=l[r]; int min=1000000000,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++){
		for(int i=1;i<=n;i++)
			if(d[i]&&min<d[i]){
				min=d[i];
				poz=i;
			}
			s[poz]=1;
			nc=l[poz];
			while(nc){
				int sc=d[poz]+nc->ct;
				if(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<<endl;
return 0;
}