#include <fstream>
#include <vector>

using namespace std;

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

const int N=50001;
const int M=250001;
const int INF=1<<30;

struct muchie{
	int x,cost;
};

vector <muchie> edge[N];

int cost[N],n,m,vizitate,heapsize;

int poz[N],heap[N];

void citire(){
	muchie aux;
	int i,a,b,c;
	in>>n>>m;
	for(i=1;i<=m;i++){
		in>>a>>b>>c;
		aux.x=b;
		aux.cost=c;
		edge[a].push_back(aux);
	}
}

inline void schimba(int a,int b){
	int x,y;
	x=heap[a];
	y=heap[b];
	heap[a]^=heap[b];
	heap[b]^=heap[a];
	heap[a]^=heap[b];
	poz[x]^=poz[y];
	poz[y]^=poz[x];
	poz[x]^=poz[y];
}

void urca(int x){
	while(x>1){
		if(cost[heap[x]]<cost[heap[x/2]]){
			schimba(x,x/2);
			x=x/2;
		}
		else{
			break;
		}
	}
}		

inline int min(int a,int b){
	return a<b? a : b;
}

void elimin(){
	int x;
	schimba(1,heapsize);
	--heapsize;
	x=1;
	while(cost[heap[x]]>min(cost[heap[2*x]],cost[heap[2*x+1]]) && 2*x+1<=heapsize){
		if(cost[heap[2*x]]<cost[heap[2*x+1]]){
			schimba(x,2*x);
			x=2*x;
		}
		else{
			schimba(x,2*x+1);
			x=2*x+1;
		}
	}
	if(cost[heap[x]]>cost[heap[2*x]] && 2*x<=heapsize){
		schimba(x,2*x);
		x=2*x;
	}
}

void Dijkstra(){
	int i,aux,nod=1,costaux;
	//viz[1]=true;
	for(i=2;i<=n;++i){
		cost[i]=INF;
	}
	while(vizitate!=n){
		for(i=0;i<edge[nod].size();++i){
			aux=edge[nod][i].x;
			costaux=edge[nod][i].cost;
			if(poz[aux]==-1)
				continue;
			if(cost[aux]==INF){
				++heapsize;
				cost[aux]=cost[nod]+costaux;
				heap[heapsize]=aux;
				poz[aux]=heapsize;
				urca(heapsize);
				continue;
			}
			if(cost[nod]+costaux<cost[aux]){
				cost[aux]=cost[nod]+costaux;
				urca(poz[aux]);
			}
		}
		poz[nod]=-1;
		vizitate++;
		nod=heap[1];
		elimin();
	}
}

void scriere(){
	for(int i=2;i<=n;++i){
		if(cost[i]==INF){
			out<<"0 ";
			continue;
		}
		out<<cost[i]<<" ";
	}
}

int main(){
	freopen("dijkstra.out","w",stdout);
	citire();
	Dijkstra();
	scriere();
	return 0;
}