#include <vector>
#include <utility>
#include <map>
#include <climits>
#include <fstream>
#include <queue>
#include <exception>
#include <iostream>
#define INF INT32_MAX

class Node {
public:
	int data;
	int d;
	int pi;

	bool operator <(Node& n1) {
		return this->d < n1.d;
	}
};


class Graph {
public:
	int v = 0, e = 0;
	std::vector <Node*> vertiges;
	//std::vector < std::pair < Node*, Node* > > edges;
	std::map < std::pair < int, int >, int > weight;
	std::map < int, std::vector <Node*> > adj;

	Graph() = default;
	/*Graph(const Graph& G) {
		this->v = G.v + 1;
		this->e += G.e + G.v;
		this->vertiges = G.vertiges;
		this->edges = G.edges;
		this->weight = G.weight;
		this->adj = G.adj;
		Node* s = (Node*)malloc(sizeof(Node));
		if (s == NULL)
			return;
		s->data = G.v;
		this->vertiges.push_back(s);
		for (auto node : G.vertiges) {
			this->edges.push_back(std::make_pair(s, node));
			this->adj[G.v].push_back(node);
		}
		for (int i = 0; i < G.v; i++)
			this->weight[std::make_pair(G.v, i)] = 0;
	}*/
};

void Initializare_s(Graph& G, Node& s) {
	for (auto v : G.vertiges) {
		v->d = INF;
		v->pi = -1;
	}
	s.d = 0;
}

void Relax(Node* u, Node* v, Graph& G) {
	if (unsigned(v->d) > unsigned(u->d + G.weight[std::make_pair(u->data, v->data)])) {
		v->d = u->d + G.weight[std::make_pair(u->data, v->data)];
		v->pi = u->data;
	}
}
/*
bool Bellman_Ford(Graph& G, Node& s) {
	Initializare_s(G, s);
	for (unsigned int i = 0; i < G.vertiges.size() - 1; i++)
		for (auto arc : G.edges)
			Relax(arc.first, arc.second, G);

	for (auto arc : G.edges)
		if (arc.second->d > arc.first->d + G.weight[std::make_pair(arc.first->data, arc.second->data)])
			return false;
	return true;
}*/

void Dijkstra(Graph& G, Node& s) {
	Initializare_s(G, s);
	/*auto compare = [](Node* n1, Node* n2) {return n1->d > n2->d; };
	std::priority_queue <Node*, std::vector <Node*>, decltype(compare) > q(compare);
	for (auto node : G.vertiges)
		q.push(node);
	while (!q.empty()) {
		Node* u = q.top();
		q.pop();
		for (auto v : G.adj[u->data]) {
			Relax(u, v, G);
		}
	}*/
	auto compare = [](Node* n1, Node* n2) {return n1->d > n2->d; };
	std::priority_queue <Node*, std::vector <Node*>, decltype(compare) > q(compare);
	for (auto node : G.vertiges)
		q.push(node);
	int cont = 0;
	std::vector <bool> visited;
	for (int i = 0; i < G.v; i++)
		visited.push_back(false);
	while (cont < G.v) {
		Node* current = q.top();
		q.pop();

		if (visited[current->data] == false) {
			++cont;
			visited[current->data] = true;
			for (auto v : G.adj[current->data]) {
				Relax(current, v, G);

				if(visited[v->data] == false)
					q.push(v);
			}
		}
	}
}

/*
std::vector < std::vector < int > > Johnson(Graph& G) {
	Graph Gprim(G);
	Node* s = Gprim.vertiges[Gprim.v - 1];
	if (Bellman_Ford(Gprim, *s) == false) {
		throw std::exception("Exista circuit cu cost negativ!");
	}
	int h[1001];
	for (auto v : Gprim.vertiges)
		h[v->data] = v->d;
	for (auto edge : G.edges)
		G.weight[std::make_pair(edge.first->data, edge.second->data)] = G.weight[std::make_pair(edge.first->data, edge.second->data)] + h[edge.first->data] - h[edge.second->data];
	free(Gprim.vertiges[Gprim.v - 1]);
	std::vector < std::vector < int > > d;
	for (auto u : G.vertiges) {
		Dijkstra(G, *u);
		std::vector < int > aux;
		for (auto v : G.vertiges)
			if (G.vertiges[v->data]->d != INF)
				aux.push_back(G.vertiges[v->data]->d - h[u->data] + h[v->data]);
			else aux.push_back(G.vertiges[v->data]->d);
		d.push_back(aux);
	}
	
	return d;
}*/

int main(/*int argc, char* argv[]*/) {
	/*if (argc != 3) {
		std::cout << "Usage: " << argv[0] << " fisier_in fisier_out\n";
		return 1;
	}*/
	std::ifstream fin("dijkstra.in");
	std::ofstream fout("dijkstra.out");
	Graph G;
	int start;
	fin >> G.v >> G.e;// >> start;
	Node *nodes = (Node*)malloc(sizeof(Node)*G.v);
	for (int i = 0; i < G.v; i++) {
		nodes[i].data = i;
		G.vertiges.push_back(&nodes[i]);
	}
	
	for (int i = 0; i < G.e; i++) {
		int x, y, w;
		fin >> x >> y >> w;
		//G.edges.push_back(std::make_pair(&nodes[x - 1], &nodes[y - 1]));
		G.weight[std::make_pair(x - 1, y - 1)] = w;
		G.adj[x - 1].push_back(&nodes[y - 1]);
	}

	std::vector < std::vector < int > > d;

	/*
	try {
		d = Johnson(G);
	}
	catch (std::exception&) {
		fout << -1;
		fout.close();
		fin.close();
		return 0;
	}

	for (auto edge : G.edges) {
		fout << edge.first->data << " " << edge.second->data << " " << G.weight[std::make_pair(edge.first->data, edge.second->data)] << "\n";
	}

	for (int i = 0; i < d.size(); i++) {
		for (int j = 0; j < d[i].size(); j++)
			if (d[i][j] != INF)
				fout << d[i][j] << ' ';
			else fout << "INF ";
		fout << '\n';
	}*/

	Dijkstra(G, nodes[0]);

	for (int i = 1; i < G.v; i++) {
		if (G.vertiges[i]->d == INF)
			fout << "0 ";
		else fout << G.vertiges[i]->d << ' ';
	}

	free(nodes);
	fout.close();
	fin.close();
}