#include <fstream>
#include <vector>
#include <queue>

int N;
std::vector<std::pair<int, int>> G[50001];

#define INFINITY 2147483647

int d[50001];
int v[50001];

struct cmp {
	bool operator()(int x, int y) {
		return d[x] > d[y];
	}
};

std::priority_queue<int, std::vector<int>, cmp> nodes;

void dijkstra(int s) {
	int i;

	for (i = 1; i <= N; ++i)
		d[i] = INFINITY;

	d[s] = 0;
	nodes.push(s);
	v[s] = 1;

	int min;
	//d[0] = INFINITY;

	for (int k = 1; k <= N; ++k) {
		//min = 0;

		/*for (i = 1; i <= N; ++i) {
			if (v[i] == 0 && d[i] < d[min])
				min = i;
		}*/

		if (!nodes.empty()) {
			min = nodes.top();
			nodes.pop();

			v[min] = 1;

			for (auto& nod : G[min]) {
				if (v[nod.first] == 0 && d[nod.first] > d[min] + nod.second) {
					d[nod.first] = d[min] + nod.second;
					nodes.push(nod.first);
				}
			}
		}
	}
}

int main() {
	std::ifstream fin("dijkstra.in");
	std::ofstream fout("dijkstra.out");

	int M;

	fin >> N >> M;

	int A, B, C;

	for (int i = 1; i <= M; ++i) {
		fin >> A >> B >> C;

		G[A].push_back({ B, C });
	}

	fin.close();

	dijkstra(1);

	for (int i = 2; i <= N; ++i) {
		if (d[i] == INFINITY)
			fout << 0;
		else
			fout << d[i];
		fout << ' ';
	}
	fout << '\n';

	fout.close();

	return 0;
}