#include "pch.h"
#include <fstream>
#include<vector>
#include<queue>
using namespace std;
#define NMAX 50005
#define INF 0x3f3f3f3f
vector<pair<int, int> > G[NMAX];
int d[NMAX], viz[NMAX];
int n, m, a, b, c;
struct cmp {
	inline bool operator() (const int i, const int j)
	{
		return d[i] > d[j];
	}
};
int main() {
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");

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

	memset(d, INF, sizeof(d));
	d[1] = 0;
	priority_queue <  int, vector < int >, cmp > q;
	q.push(1);
	while (!q.empty()) {
		int a = q.top();
		viz[a] = 0;
		q.pop();

		for (int i = 0; i < G[a].size(); i++) {
			b = G[a][i].first;
			c = G[a][i].second;
			if (d[b] > d[a] + c) {
				d[b] = d[a] + c;
				if (!viz[b]) {
					viz[b] = 1;
					q.push(b);
				}
			}
		}
	}

	for (int i = 2; i <= n; i++) {
		if (d[i] == INF) {
			d[i] = 0;
		}
		g << d[i] << ' ';
	}
}