#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <functional>
#include <algorithm>

#define NMAX 50001
#define INF  (1<<30)
#define SRC  1

using namespace std;

int n, m;
list<pair<int, int>> graph[NMAX];
int dist[NMAX];
priority_queue<int, vector<int>, function<bool(int, int)>> q(
	[](int a, int b) {
		return dist[a] < dist[b];
	}
);
bool visited[NMAX];

void dijkstra()
{
	// initialization
	fill_n(dist, n + 1, INF);
	dist[SRC] = 0;
	q.push(SRC);

	// main loop
	while (!q.empty()) {
		int a = q.top();
		q.pop();
	
		if (visited[a])
			continue;
		visited[a] = true;

		for (auto bc : graph[a]) {
			int alt = dist[a] + bc.second;
			if (alt < dist[bc.first]) {
				dist[bc.first] = alt;
				q.push(bc.first);
			}
		}
	}
}

int main()
{
	int a, b, c;

	// read input
	ifstream fin("dijkstra.in");

	fin >> n >> m;
	for (int i = 0; i < m; i++) {
		fin >> a >> b >> c;
		graph[a].push_back(make_pair(b, c));
	}

	fin.close();

	// solve
	dijkstra();
	
	// print output
	ofstream fout("dijkstra.out");

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

	fout.close();

	return 0;
}