#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <set>
#include <limits>

#define Inf 1000000

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m;
vector< list<pair<int,int>> > adjacencies;

struct Comparator {
	bool operator()(pair<int, int> p1, pair<int, int>p2) {
		return p1.second > p2.second;
	}
}; 

vector<int> dijkstra(vector<list<pair<int, int>>> adjacencies, int n, int src) {
	vector<int> dist(n+1);
	vector<int> prev(n+1);
	dist[src] = 0;
	set<pair<int, int>, Comparator> queue_container;
	
	for (int i = 1; i <= n; i++) {
		if (i != src) {
			dist[i] = Inf;
			prev[i] = 0;
		}
		queue_container.insert(pair<int, int>(i, dist[i]));
	}
	
	while (queue_container.size()) {
		//extrag perechea <key, dist> cea mai mica
		pair<int, int> vp = *queue_container.begin();
		queue_container.erase(vp);
		int u = vp.first;
		int cost = vp.second;

		for (list<pair<int, int>>::iterator it = adjacencies[u].begin();
			it != adjacencies[u].end(); it++) {
			pair<int, int> edge = *it;
			int candidate = dist[u] + edge.second;
			if (candidate < dist[edge.first]) {
				//elimin din coada pentru actualizarea prioritatii
				queue_container.erase(pair<int, int>(edge.first, dist[edge.first]));
				dist[edge.first] = candidate;
				prev[edge.first] = u;
				//reinserez
				queue_container.insert(pair<int, int>(edge.first, candidate));
			}
		}
	}
	return dist;
}

int main(void) {

	fin >> n >> m;
	adjacencies = vector< list<pair<int,int>> >(n+1);
	pair<int, int> a = pair<int, int>(0, 0);

	for (int i = 0; i <= m; i++) {
		int src, dst, cost;
		fin >> src >> dst >> cost;
		adjacencies[src].push_back(pair<int, int>(dst, cost));
	}

	vector<int> dist = dijkstra(adjacencies, n, 1);
	for (int i = 2; i <= n; i++) {
		fout << dist[i] << ' ';
	}
	fout << endl;

	fin.close();
	fout.close();
	return 0;
}