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

using namespace std;

int m, n;

vector<pair<int, int> > g[50001];
unsigned dist[50001];
unsigned route[50001];

struct Cmp
{

	bool operator()(int x, int y)
	{
		return dist[x] > dist[y];
	}
};

int main(int argc, char** argv)
{
	ifstream ifs("dijkstra.in");

	ifs >> n >> m;

	for (int i = 0; i < m; ++i) {
		int from, to, weight;
		ifs >> from >> to >> weight;
		g[from].push_back(make_pair(to, weight));
	}

	for (int i = 0; i < m; ++i) {
		dist[i] = -1;
	}



	priority_queue<int, vector<int>, Cmp> q;
	q.push(1);
	dist[1] = 0;

	while (!q.empty()) {
		int node = q.top();
		q.pop();

		for (int i = 0; i < g[node].size(); ++i) {
			int target = g[node][i].first;
			int newdist = dist[node] + g[node][i].second;
			if (newdist < dist[target]) {
				q.push(target);
				route[target] = node;
				dist[target] = newdist;
			}
		}
	}

	//	vector<int> path;
	//	int node = n;
	//	while (node != 1) {
	//		path.push_back(node);
	//		node = route[node];
	//	}
	//	reverse(path.begin(), path.end());
	//
	//	cout << 1 << endl;
	//	for (int i = 0; i < path.size(); ++i) {
	//		cout << " " << path[i];
	//	}

	ofstream ofs("dijkstra.out");
	for (int i = 2; i <= n; ++i)
		ofs << (dist[i] == -1 ? 0 : dist[]) << " ";

	return 0;
}