#include <fstream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <algorithm>
#include <set>

#define MAX_VERTEXES 20000
#define INF 1e18

using namespace std;

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

struct Edge {
	int cost;
	int destinationVertex;
};

struct Vertex {
	vector<Edge> edges;
};

int N, M;
vector<Vertex> vertexes(MAX_VERTEXES + 1);

void dijkstra() {
	vector<long long> distances(N + 1);
	vector<bool> visited(N + 1);
	set<pair<long long, int>> s;

	for (int i = 1; i <= N; ++i) {
		distances[i] = INF;
	}

	distances[1] = 0;
	s.insert(make_pair(0, 1));

	while (!s.empty()) {
		int currentVertexLabel = s.begin()->second;

		visited[currentVertexLabel] = true;
		s.erase(s.begin());

		for (auto edge : vertexes[currentVertexLabel].edges) {
			if (!visited[edge.destinationVertex]) {
				if (distances[currentVertexLabel] + edge.cost < distances[edge.destinationVertex]) {
					if (s.find(make_pair(distances[edge.destinationVertex], edge.destinationVertex)) != s.end()) {
						s.erase(s.find(make_pair(distances[edge.destinationVertex], edge.destinationVertex)));
					}

					s.insert(make_pair(distances[currentVertexLabel] + edge.cost, edge.destinationVertex));

					distances[edge.destinationVertex] = distances[currentVertexLabel] + edge.cost;
				}
			}
		}
	}

	for (int i = 2; i <= N; ++i) {
		if (distances[i] == INF) {
			cout << 0 << ' ';
		}
		else {
			cout << distances[i] << ' ';
		}
	}
}

int main() {
	int v1, v2, c;

	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		cin >> v1 >> v2 >> c;

		Edge edge;
		edge.cost = c;
		edge.destinationVertex = v2;

		vertexes[v1].edges.push_back(edge);
	}

	dijkstra();
}