#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 5e4;
const int INF = 1e9;

int n, m;
int dist[NMAX + 1], freq[NMAX + 1];
vector<pair<int, int>> adj[NMAX + 1];

void DEsopoPape(int u = 1) {
	for(int i = 2; i <= n; i++) {
		freq[i] = 2;
	}
	for(int i = 2; i <= n; i++) {
		dist[i] = INF;
	}
	deque<int> DS; // <3
	DS.push_back(u);
	dist[u] = 0;

	while(!DS.empty()) {
		int v = DS.front();
		DS.pop_front();
		freq[v] = 0;

		for(const auto &it: adj[v]) {
			if(dist[v] + it.second < dist[it.first]) {
				dist[it.first] = dist[v] + it.second;

				if(freq[it.first] == 2) {	
					freq[it.first] = 1;
					DS.push_back(it.first);
				} else if(freq[it.first] == 0) {
					freq[it.first] = 1;
					DS.push_back(it.first);
				}
			}
		}
	}
}

int main() {
	fin >> n >> m;

	for(int i = 1; i <= m; i++) {
		int u, v, c;
		fin >> u >> v >> c;

		adj[u].push_back({v, c});
	}

	DEsopoPape();

	for(int i = 2; i <= n; i++) {
		fout << dist[i] << " ";
	}
	fout << '\n';
	return 0;
}