#include <fstream>
#include <queue>

using namespace std;

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

const int MAX_N = 50005;
const int INF = 0x3f3f3f3f;

int n, m, D[MAX_N];
vector < pair<int, int> > L[MAX_N];
priority_queue < pair<int, int> > H;

void read() {
	f >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b, c;
		f >> a >> b >> c;
		L[a].push_back(make_pair(b, c));
	}
}

void init() {
	for (int i = 1; i <= n; i++)
		D[i] = INF;
	D[1] = 0;
}

void solve() {
	H.push (make_pair(1, D[1]));
	while (!H.empty()) {
		pair <int, int> X = H.top();	H.pop();
		int nod = X.first;	int dist = X.second;
		
		for (int i = 0; i < L[nod].size(); i++) {
			if (dist + L[nod][i].second < D[L[nod][i].first]) {
				D[L[nod][i].first] = dist + L[nod][i].second;
				H.push ( make_pair(L[nod][i].first, D[L[nod][i].first]) );
			}
		}
	}
}

void write() {
	for (int i = 2; i <= n; i++)
		if (D[i] != INF)
			g << D[i] << " ";
		else
			g << 0 << " ";
}

int main() {
	read();
	init();
	solve();
	write();
	
	f.close();
	g.close();
	
	return 0;
}