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

#define Inf std::numeric_limits<int>::max()
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(int n, int src) {
	vector<int> dist(n+1);
	fill(dist.begin(), dist.end(), Inf);
	dist[src] = 0;
	priority_queue<pair<int, int>, vector<pair<int, int>>, Comparator> Q;
	Q.push(pair<int, int>(src, 0));
	while (!Q.empty()) {
		//extrag perechea <key, dist> cea mai mica
		pair<int, int> vp = Q.top();
		Q.pop();
		int u = vp.first;
	
		for (auto &it: adjacencies[u]) {
			pair<int, int> edge = it;
			if (dist[u] + edge.second < dist[edge.first]) {
				dist[edge.first] = dist[u] + edge.second;
				Q.push(pair<int,int>(edge.first, dist[edge.first]));
			}
		}
	}
	return dist;
}

int main(void) {

	fin >> n >> m;
	adjacencies = vector< list<pair<int,int>> >(n+1);
	
	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(n, 1);
	for (int i = 2; i <= n; i++) {
		if(dist[i] != Inf) fout << dist[i] << ' ';
		else fout << 0 << ' ';
	}
	fout << endl;

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