#include <fstream>
#include <vector>

#define INF (1<<30)
#define max_n 50001
#define max_m 250001
#define inf first
#define c second
#define mp make_pair

using namespace std;

int n,m,nr,nod,x,y,i,cost;
vector < pair < int,int > > g[max_n];
vector < pair < int,int > > :: iterator it;
int h[max_n],poz[max_n],d[max_n];



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

void swap1(int i,int j) {
	int aux;
	aux=h[i];
	h[i]=h[j];
	h[j]=aux;
	poz[h[i]]=i;
	poz[h[j]]=j;
}
	
void HeapUp(int k) {
	int t;
	if (k<=0) return;
	t=(k-1)/2;
	if (d[h[t]]>d[h[k]]) {
		swap1(k,t);
		HeapUp(t);
	}
}
		

void BuildHeap() {
	int i;
	for (i=1; i<n; i++) HeapUp(i);
}

void HeapDown(int r,int k) {
	int st,dr,i,q;
	if (2*r+1<=k) {
		q=2*r+1;
		st=h[q];
		if (q+1<=k) dr=h[q+1];
		else dr=st-1;
		if (st>dr) i=q;
		else i=q+1;
		if (d[h[r]]>d[h[i]]) {
			swap1(r,i);
			HeapDown(i,k);
		}
	}
}

int min_heap() {  //minimul
	swap1(0,nr-1);
	poz[h[nr-1]]=0;
	nr--;
	HeapDown(0,nr-1);
    return h[nr];
}

int main () {
	in >> n >> m;
	for (i=1; i<=m; i++) {
		in >> x >> y >> cost;
		g[x].push_back(mp(y,cost));
	}
	for (i=0; i<n; i++) {
		h[i]=i+1;
		poz[i+1]=i;
		d[i+1]=INF;
	}
	//memset(ok,false,sizeof(ok));
	d[1]=0;
	BuildHeap();
	nr=n;
	while (nr) {
		nod=min_heap();
		for (it=g[nod].begin(); it!=g[nod].end(); it++) 
			if (d[(*it).inf] > d[nod] + (*it).c ) {
				d[(*it).inf] = d[nod] + (*it).c;
				HeapUp(poz[(*it).inf]);
			}
	}
	
	for (i=2; i<=n; i++) 
		if (d[i]!=INF) out << d[i] << ' ';
	    else out << "0 ";
	out << '\n';
	in.close();
	out.close();
	return 0;
}