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

using namespace std;

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

const int dim = 50001;
int d[dim], nodes, edges;
bool inQ[dim];

vector< pair<int, int> >graph[dim];

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

priority_queue<int, vector<int>, cmpD>q;

void input() {
	in >> nodes >> edges;
	for (int i = 0; i < edges; i++) {
		int u, v, c;
		in >> u >> v >> c;
		graph[u].push_back(make_pair(v, c));
	}
}

void dijkstra(int node) {

	for (int i = 1; i <= nodes; i++) {
		d[i] = INT_MAX;
	}
	d[node] = 0;
	q.push(node);
	inQ[node] = true;

	while (q.empty() == false) {
		int u = q.top();
		q.pop();
		inQ[u] = false;
		for (size_t y = 0; y < graph[u].size(); y++) {

			int v = graph[u][y].first;
			int c = graph[u][y].second;
			if (d[v] > d[u] + c) {
				d[v] = d[u] + c;
				if (!inQ[v]) {
					q.push(v);
					inQ[v] = true;
				}
			}
		}
	}
}

int main() {

	input();
	dijkstra(1);
	for (int i = 2; i <= nodes; i++) {
		if (d[i] == INT_MAX) {
			out << "0 ";
		}
		else {
			out << d[i] << " ";
		}
	}

	return 0;
}