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

#define NMAX 50005
#define MAX_VALUE 1000000000

using namespace std;

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

int min_dist[NMAX];

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

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

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

		nodes.pop();
		in_q[element.second] = 0;

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

				if (!in_q[it.second]) {
					nodes.push(make_pair(-min_dist[it.second], it.second));
					in_q[it.second] = 1;
				}
			}
		}
	}
}

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;
		in_q[i] = 0;
	}

	dijkstra(1);

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