#include <iostream>
#include <fstream>
#include <vector>

#define MAXN 50050
#define INF 1000000

using namespace std;

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

struct Node {
	int at;
	int cost;
};

vector<Node> G[MAXN];

int pre[MAXN];
int vis[MAXN];
int d[MAXN];
int N,M;

void read_f() {
	fin >> N >> M;
	int x,y,c,i;
	Node tmp;
	
	for (i=1;i<=N;++i) d[i] = INF;
	
	for (i=0;i<M;++i) {
		fin >> x >> y >> c;
		tmp.at = y;
		tmp.cost = c;
		G[x].push_back(tmp);
		if (x == 1) {
			d[y] = c;
		}
	}
	
	for (i=1;i<=N;++i) pre[i] = 1;
	d[1] = 0;
	pre[1] = 0; vis[1] = 1;
}

void dijkstra() {
	int i,j,VfMin,DMin;
	
	for (j=1;j<N;++j) {
		
		DMin = INF;
		for (i=1;i<=N;++i) {
			if (!vis[i] && d[i] < DMin) {
				DMin = d[i];
				VfMin = i;
			}
		}
		
		vis[VfMin] = 1;
		for (i=0;i<G[VfMin].size();++i) {
			if (d[G[VfMin][i].at] > d[VfMin] + G[VfMin][i].cost) {
				d[G[VfMin][i].at] = d[VfMin] + G[VfMin][i].cost;
				pre[G[VfMin][i].at] = VfMin;
			}			
		}
		
	}
}

void write_f() {
	int i;
	for (i=2;i<=N;++i) fout << ((d[i] == INF)?0:d[i]) << " ";
	fout << "\n";
}

int main() {

	read_f();
	dijkstra();
	write_f();
	
	fin.close();
	fout.close();

	return 0;
}