#include <fstream>
#include <vector>
#include <set>

#define INFINITE 1000000000

std::ifstream fin("dijkstra.in", std::ifstream::in);
std::ofstream fout("dijkstra.out", std::ofstream::out);
void dijkstra(std::vector< std::vector< std::pair<int, int> > >& graph, int node);

int main() {
	int n, m, tmp1, tmp2, tmp3;
	fin >> n >> m;
	std::vector< std::vector< std::pair<int, int> > > graph(n + 1);

	for (int i = 0; i < m; i++) {
		fin >> tmp1 >> tmp2 >> tmp3;
		graph[tmp1].push_back(std::make_pair(tmp2, tmp3));
	}

	dijkstra(graph, 1);
}

void dijkstra(std::vector< std::vector< std::pair<int, int> > >& graph, int node) {
	std::vector<int> dist(graph.size() + 1, INFINITE);
	std::set<std::pair<int, int>> noduri;
	
	dist[node] = 0;

	for (int i = 1; i <= graph.size(); i++) 
		noduri.insert(std::make_pair(dist[i], i));

	for (int i = 1; i < graph.size(); i++) {
		// retin nodul cu dist minima
		int min_node = noduri.begin()->second;
		// extrag nodul din lista
		noduri.erase(noduri.begin());

		// parcurg vecinii si relaxez muchiile
		for (int j = 0; j < graph[min_node].size(); j++) {
			
			int dist_alt = dist[min_node] + graph[min_node][j].second;

			if (dist_alt < dist[graph[min_node][j].first]) {
				noduri.erase(std::make_pair(dist[graph[min_node][j].first], graph[min_node][j].first));
				dist[graph[min_node][j].first] = dist_alt;
				noduri.insert(std::make_pair(dist_alt, graph[min_node][j].first));
			}
		}
	}

	for (int i = 2; i < graph.size(); i++) {
		if (dist[i] == INFINITE) dist[i] = 0;
		fout << dist[i] << ' ';
	}
}