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

using namespace std;

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


vector<pair<int, int> > v[50005];

void read(int &N, int &M) {

	int x, y, z;

	f >> N >> M;
	for (int i = 0; i < M; ++i) {
		f >> x >> y >> z;
		v[x].push_back(make_pair(y, z));
	}
}


void dfs(int *dist, bool *visited) {

	queue <int> q;
	int node;
	dist[1] = 0;
	visited[1] = true;
	q.push(1);

	while (q.size()) {
		node = q.front();
		q.pop();

		visited[node] = false;

		for (auto &x : v[node]) {
			if (dist[x.first] > dist[node] + x.second) {
				dist[x.first] = dist[node] + x.second;
				if (visited[x.first] == false) {
					visited[x.first] = true;
					q.push(x.first);
				}
			}
		}
	}


}

int main()
{
	const int Max = numeric_limits<int>::max();
	int N, M;
	int dist[50005];
	bool visited[50005];

	read(N, M);

	for (int i = 1; i <= N; ++i) {
		dist[i] = Max;
		visited[i] = false;
	}

	dfs(dist, visited);

	for (int i = 2; i <= N; ++i) {
		if (dist[i] == Max) g << "0 ";
		else g << dist[i] << " ";
	}
	return 0;
}