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

using namespace std;

int m, n;

vector<pair<unsigned short, short> > 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 cin("dijkstra.in");

	cin >> n >> m;

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

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

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

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

		for (size_t i = 0; i < g[node].size(); ++i) {
			unsigned short target = g[node][i].first;
			unsigned 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 cout("dijkstra.out");
	for (int i = 2; i <= n; ++i)
		cout << (dist[i] == (unsigned)-1 ? 0 : dist[i]) << " ";

	return 0;
}