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

	for (;;) {
		int node = q.top();
		q.pop();

		if (node == n)
			break;

		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] << " ";
	
	return 0;
}