#include <fstream>
#include <vector>
#define MAX 60010
#define INF 2000000000
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 swap(int i,int j){
	int aux=heap[i];heap[i]=heap[j];heap[j]=aux;
	poz[heap[i]]=i;poz[heap[j]]=j;
}

void heap_up(int pos){
	int dad=pos/2;
	if (dad){
		if (D[heap[dad]]>D[heap[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<=dheap && D[heap[left]]<D[heap[nod]]) minim=left;
	if (right<=dheap && D[heap[right]]<D[heap[minim]]) minim=right;
	if (minim!=nod){
		swap(nod,minim);
		heap_dw(poz[minim]);
	}
}

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

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