#include <fstream>
#include <vector>
#define MAX 60010
#define INF 2000000000
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
int D[MAX],P[MAX],H[MAX];
int DH;
int N,M;
vector<pair<int,int> > vecini[MAX];


void citire(){
	fi>>N>>M;
	pair<int,int> Pr;
	int x,y,z;
	for (int i=1;i<=M;++i){
		fi>>x>>y>>z;
		Pr.first=y;Pr.second=z;
		vecini[x].push_back(Pr);
	}
	fi.close();
}

void swap(int i,int j){
	int aux=H[i];H[i]=H[j];H[j]=aux;
	P[H[i]]=i;P[H[j]]=j;
}

void heap_up(int pos){
	int dad=pos/2;
	if (dad){
		if (D[H[dad]]>D[H[pos]]){
			swap(pos,dad);
			heap_up(dad);
		}
	}
}

void heap_dw(int nod){
	int left=nod*2;
	int right=left+1;
	int minim=nod;
	if (left<=DH && D[H[left]]<D[H[nod]]) minim=left;
	if (right<=DH && D[H[right]]<D[H[minim]]) minim=right;
	if (minim!=nod){
		swap(nod,minim);
		heap_dw(minim);
	}
}

int extract_min(){
	swap(1,DH);
	--DH;
	heap_dw(1);
	return H[DH+1];
}

void dijkstra(int sursa){
	DH=N;
	for (int i=1;i<=N;++i) { D[i]=INF;P[i]=i;H[i]=i;}
	D[sursa]=0;
	heap_up(P[sursa]);
	while(DH){
		int toupdate=extract_min();
		for (unsigned int j=0;j<vecini[toupdate].size();++j) {
			int newnod=vecini[toupdate][j].first;
			int newcost=D[toupdate]+vecini[toupdate][j].second;
			if (D[newnod]>newcost){
				D[newnod]=newcost;
				heap_up(P[newnod]);
			}
		}
	}
}

void solve(){
	dijkstra(1);
	for (int i=2;i<N;++i) {
		if (D[i]!=INF){
			fo<<D[i]<<" "; } else {fo<<"0 ";}
	}
	if (D[N]!=INF){
		fo<<D[N]<<"\n";} else {fo<<"0\n";}

	fo.close();
}


int main(){
	citire();
	solve();
	return 0;
}