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

#define NMAX 50005
#define MAX_VALUE 1000000000

using namespace std;

vector <pair <int, int> > edges[NMAX];

int min_dist[NMAX];

void dijkstra(int source) {
	priority_queue <pair <int, int> > nodes;

	nodes.push(make_pair(0, source));
	min_dist[source] = 0;

	while (!nodes.empty()) {
		pair<int, int> element = nodes.top();

		nodes.pop();

		for (auto it : edges[element.second]) {
			if (-element.first + it.first < min_dist[it.second]) {
				min_dist[it.second] = -element.first + it.first;
				nodes.push(make_pair(-min_dist[it.second], it.second));
			}
		}
	}
}

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

	int n, m, x, y, z;

	f >> n >> m;
	for (int i = 0; i < m; i++) {
		f >> x >> y >> z;
		edges[x].push_back(make_pair(z, y));
	}
	for (int i = 2; i <= n; i++)
		min_dist[i] = MAX_VALUE;

	dijkstra(1);

	for (int i = 2; i <= n; i++) {
		g << (min_dist[i] != MAX_VALUE ? min_dist[i] : 0) << " ";
	}
}