#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include <queue>
#include <functional>
#include <utility>
#define MAX 50005
#define INF 1000000000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

vector<pair<int, int> > graph[MAX];
int dist[MAX];
bool viz[MAX];

void Dijkstra(int start, int n, int m);
class comp {
public:
	bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
		return (a.second > b.second) ? true : false;
	}
};

int main() {
	int n, i, x, y, c, m;

	fin >> n >> m;

	for (i = 0; i < m; ++i) {
		fin >> x >> y >> c;

		graph[x].push_back({ y, c });
	}

	Dijkstra(1, n, m);

	for (i = 2; i <= n; ++i)
		fout << (dist[i] == INF ? 0 : dist[i]) << ' ';

	return 0;
}

void Dijkstra(int start, int n, int m) {
	int x, cost, i;

	for (i = 1; i <= n; ++i) {
		dist[i] = INF;
		viz[i] = false;
	}

	priority_queue<pair<int, int>, vector<pair<int, int> >, comp> pq;

	dist[start] = 0;
	pq.push(make_pair(start, 0));

	while (!pq.empty()) {
		x = pq.top().first;

		pq.pop();

		if (viz[x] == false) {
			viz[x] = true;

			vector<pair<int, int> >::iterator it;
			for (it = graph[x].begin(); it != graph[x].end(); ++it) {
				int y = it->first;
				cost = it->second;

				if (dist[y] > dist[x] + cost) {
					dist[y] = dist[x] + cost;
					pq.push(make_pair(y, dist[y]));
				}
			}
		}
	}
}