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

#define NMax 50004
#define oo 2000000000

using namespace std;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
int N, M, a, b, c, dist[NMax];
bool visited[NMax];

vector <pair <int, int>> G[NMax];

priority_queue <pair <int, int>> pq;
 
int main() {
 
	int i, currentNode;

    fin >> N >> M;

	for (i = 1; i <= M; i++) {
		fin >> a >> b >> c;
		G[a].push_back({ b, c });
	}
	
	for (i = 2; i <= N; i++) {
		dist[i] = oo;
	}
	
	pq.push({ 0, 1 });
	
	while (!pq.empty()) {
		currentNode = pq.top().second;
		pq.pop();

		if (!visited[currentNode]) {
			visited[currentNode] = true;

			for (auto node : G[currentNode]) {
				if (dist[currentNode] + node.second < dist[node.first]) {
					dist[node.first] = dist[currentNode] + node.second;
					pq.push({ -dist[node.first], node.first });
				}
			}
		}
	}

	for (i = 2; i <= N; i++) {
		if (dist[i] == oo) {
			fout << "0 ";
		}
		else {
			fout << dist[i] << " ";
		}
	}
 
    fin.close();
    fout.close();

    return 0;
}