#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];

struct node {
	int id;
	int dist;
};
priority_queue<node, vector<node>, function<bool(node, node)>> q(
	[](node a, node b) {
		return a.dist > b.dist;
	}
);

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

	// main loop
	while (!q.empty()) {
		node a = q.top();
		q.pop();
	
		// if visited continue
		if (dist[a.id] != INF)
			continue;
		dist[a.id] = a.dist;

		for (auto bc : graph[a.id])
			q.push({bc.first, a.dist + bc.second});
	}
}

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;
}