#include<fstream>
#include<vector>
#include<algorithm>

using namespace std;

#define f first
#define s second

const int Nmax = 50001;
const int INF = 1<<30;

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

vector<pair<int, int> > G[Nmax];
pair<int, int> aint[131072];
int N, M, D[Nmax];
int val, poz;

void build(int nod, int st, int dr) {
	
	if(st == dr) {
		aint[nod] = make_pair(INF, st);
		return;
	}
	
	int mij = (st+dr)/2;
	build(2*nod, st, mij);
	build(2*nod+1, mij+1, dr);
	
	aint[nod] = min(aint[2*nod], aint[2*nod+1]);
}

void update(int nod, int st, int dr) {
	
	if(st == dr) {
		aint[nod] = make_pair(val, st);
		return;
	}
	
	int mij = (st+dr)/2;
	if(poz <= mij)
		update(2*nod, st, mij);
	else
		update(2*nod+1, mij+1, dr);
	
	aint[nod] = min(aint[2*nod], aint[2*nod+1]);
}

void dijkstra(int source) {
	
	int i, nod, son, cost;
	vector<pair<int, int> >:: iterator it;
	
	D[source] = 0;
	poz = source; val = 0;
	update(1, 1, N);
	
	for(i=1; i<=N; ++i) {
		nod = aint[1].s;
		
		poz = aint[1].s; val = INF;
		update(1, 1, N);
		
		for(it=G[nod].begin(); it!=G[nod].end(); ++it) {
			son = it->f; 
			cost = it->s;
			if(D[son] > D[nod] + cost) {
				D[son] = D[nod] + cost;
				poz = son; val = D[son];
				update(1, 1, N);
			}
		}
	}
}

int main() {
	
	int i, j, c;
	
	f>>N>>M;
	while(M--) {
		f>>i>>j>>c;
		G[i].push_back(make_pair(j,c));
	}
	
	build(1, 1, N);
	fill(D+1, D+N+1, INF);
	
	dijkstra(1);
	
	for(i=2; i<=N; ++i)
		if(D[i] == INF)
			g<<"0 ";
		else
			g<<D[i]<<" ";
	g<<"\n";
	
	f.close(); g.close();
	
	return 0;
}