#include <fstream>
#include <vector>

using namespace std;

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

const int nmax = 5e4;
const long long INF = 125e8;

struct edge {

	int b;
	long long cost;

	edge(int y = 0, long long z = 0) {

		b = y, cost = z;
	}
};

struct node {

	int index;
	long long tentative;

	node(int a = 0, long long b = INF) {

		index = a, tentative = b;
	}
};

int n, m;
vector<edge> edges[nmax + 1];

node unvisited[nmax * 4];
int last = 0, lookup[nmax + 1], minpaths[nmax + 1];

void minHeapify(int pos) {
		
	int new_pos = pos;
	if (pos * 2 <= last && unvisited[new_pos].tentative > unvisited[pos * 2].tentative)
		new_pos = pos * 2;
	if (pos * 2 + 1 <= last && unvisited[new_pos].tentative > unvisited[pos * 2 + 1].tentative)
		new_pos = pos * 2 + 1;

	if (new_pos == pos)
		return;

	swap(unvisited[pos], unvisited[new_pos]);
	lookup[unvisited[pos].index] = pos;
	lookup[unvisited[new_pos].index] = new_pos;
	minHeapify(new_pos);
}

void moveUp(int curr_pos) {

	while (curr_pos > 1) {

		if (unvisited[curr_pos].tentative < unvisited[curr_pos >> 1].tentative) {

			swap(unvisited[curr_pos], unvisited[curr_pos >> 1]);
			lookup[unvisited[curr_pos].index] = curr_pos;
			lookup[unvisited[curr_pos >> 1].index] = curr_pos >> 1;
			curr_pos = curr_pos >> 1;
		}
		else
			break;
	}
}

void insert(node to_insert) {

	int curr_pos = ++last;
	unvisited[curr_pos] = to_insert;

	lookup[unvisited[curr_pos].index] = curr_pos;
	moveUp(curr_pos);
}

node extractMin() {

	node min = unvisited[1];
	minpaths[min.index] = min.tentative;
	lookup[unvisited[1].index] = 0;
	unvisited[1] = unvisited[last--];
	lookup[unvisited[1].index] = 1;

	minHeapify(1);

	return min;
}

void decreaseKey(int index, long long val) {

	unvisited[lookup[index]].tentative = val;

	moveUp(lookup[index]);
}

int main() {

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {

		int x, y;
		long long z;

		cin >> x >> y >> z;

		edges[x].push_back(edge(y, z));
	}

	insert(node(1, 0));
	for (int i = 2; i <= n; i++)
		insert(node(i));

	while (unvisited[1].tentative != INF) {

		node top = extractMin();

		for (edge e : edges[top.index]) {

			if (lookup[e.b]) {

				decreaseKey(e.b, min(unvisited[lookup[e.b]].tentative, top.tentative + e.cost));
			}
		}
	}

	for (int i = 2; i <= n; i++)
		cout << minpaths[i] << " ";
}