#include <fstream>
#include <vector>

#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 min_dist_node(std::vector< std::vector< std::pair<int, int> > >& graph, std::vector<int>& noduri);

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::vector<int> noduri(graph.size() + 1, INFINITE);

	dist[node] = noduri[node] = 0;

	for (int i = 1; i <= graph.size(); i++) {
		// retin nodul cu dist minima
		int min_node = min_dist_node(graph, noduri);
		// extrag nodul din lista
		noduri[min_node] = INFINITE;

		// 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]) {
				dist[graph[min_node][j].first] = dist_alt;
				noduri[graph[min_node][j].first] = dist_alt;
			}
		}
	}

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

int min_dist_node(std::vector< std::vector< std::pair<int, int> > >& graph, std::vector<int>& noduri) {
	int min_dist_node = INFINITE;
	int min_node = 0;
	for (int i = 1; i <= graph.size(); i++)
		if (min_dist_node > noduri[i]) {
			min_dist_node = noduri[i];
			min_node = i;
		}
	return min_node;
}