#include <fstream>
#include <vector>
#include <queue>
#define inf 0xFFFFFFFF >> 1

using namespace std;

ifstream fin("C:/Facultate/dijkstra.in");
ofstream fout("C:/Facultate/dijkstra.out");

vector<pair<int, int>> g[(int)5e4 + 5];
vector<int> d;

void dijkstra(int start, int n) {
	d = vector<int>(n + 1, inf);
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;	
	vector<bool> vis = vector<bool>(n + 1, false);
	
	d[start] = 0;
	pq.push({d[start], start});

	while(!pq.empty()) {
		int node = pq.top().second;
		int cost = pq.top().first;
		pq.pop();
		if(!vis[node]) {
			vis[node] = true;

			for(auto it: g[node]) {
				int new_node = it.first;
				int new_cost = it.second;

				if(d[new_node] > d[node] + new_cost) {
					d[new_node] = d[node] + new_cost;
					pq.push({d[new_node], new_node});
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	fin.tie(0), fout.tie(0);

	int n, m;

	fin >> n >> m;

	for(int i = 0, u, v, cost; i < m; i++) {
		fin >> u >> v >> cost;
		g[u].push_back({v, cost});
	}

	dijkstra(1, n);

	for(int i = 2; i <= n; i++)
		if(d[i] == inf)
			fout << 0 << ' ';
		else fout << d[i] << ' ';
	
	fin.close();
	fout.close();
	return 0;
}