#include<fstream>
#include<queue>
#include<vector>
#include<functional> // greater
#include<utility> // pair
using namespace std;

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

int n, m;
vector< pair<int, int> > adj[50000];
int dist[50000];

int main() {
	int i, u, v, c;
	pair<int, int> current;
	fin >> n >> m;
	for(i = 0; i < m; i++) {
		fin >> u >> v >> c;
		adj[u-1].push_back(make_pair(v-1, c));
	}
	for(i = 0; i < n; i++) dist[i] = 0x3f3f3f3f;

	// the type in heap will be pair<distance, node>
	priority_queue<pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > heap;
	dist[0] = 0;
	heap.push(make_pair(0, 0));

	while(!heap.empty()) {
		current = heap.top();
		heap.pop();
		if(current.first > dist[current.second]) continue; // a shorter path was introduced in the heap

		for(vector< pair<int, int> >::iterator it = adj[current.second].begin(); it != adj[current.second].end(); ++it) {
			// try to relax
			if(dist[it->first] > it->second + current.first) {
				dist[it->first] = current.first + it->second; // dist pana in vecin = dist pana in nodul curent + dist dintre noduri
				heap.push(make_pair(dist[it->first], it->first));
			}
		}
	}
	for(i = 1; i < n; i++) fout << ((dist[i] == 0x3f3f3f3f) ? 0 : dist[i]) << " ";
	return 0;
}