#include <fstream>
#include <vector>
#define MAX 60010
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
int D[MAX],poz[MAX],heap[MAX];
int dheap;
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 heap_up(int pos){
	int dad=pos/2;
	if (dad){
		if (D[heap[dad]]>D[heap[pos]]){
			int aux=heap[dad];
			heap[dad]=heap[pos];
			heap[pos]=aux;
			poz[heap[pos]]=pos;
			poz[heap[dad]]=dad;
			heap_up(dad);
		}
	}
}

void heap_dw(int nod){
	int left=nod*2;
	int right=left+1;
	int minim=nod;
	if (left<=dheap && D[heap[left]]<D[heap[nod]]) minim=left;
	if (right<=dheap && D[heap[right]]<D[heap[minim]]) minim=right;
	if (minim!=nod){
		int aux=heap[nod];
		heap[nod]=heap[minim];
		heap[minim]=aux;
		poz[heap[nod]]=nod;
		poz[heap[minim]]=minim;
		heap_dw(minim);
	}
}



void dijkstra(int sursa){
	dheap=N;
	for (int i=1;i<=N;++i) { D[i]=300000000;poz[i]=i;heap[i]=i;}
	D[sursa]=0;
	heap_up(poz[sursa]);
	while(dheap){
		int toupdate=heap[1];
		int aux=heap[1];
		heap[1]=heap[dheap];
		heap[dheap]=aux;
		poz[heap[1]]=1;
		--dheap;
		heap_dw(1);
		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(poz[newnod]);
			}
		}
	}
}

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

	fo.close();
}


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