#include <fstream>
#include <functional>
#include <climits>
#include <vector>
#include <queue>
#include <list>

using namespace std;

struct node {
	long vertex;
	long weight;
	node(long v, long w) : vertex(v), weight(w) { };
	node() { }
};

class CompareGreater {
	public:
		bool operator()(const node &nodeX, const node &nodeY) const {
			return (nodeX.weight > nodeY.weight) ;
		}
};

vector< list<node> > adj;
vector<long> weights;
priority_queue<node, vector<node>, CompareGreater> Q;

long nrVertices, nrEdges;

void readData();
void Dijkstra(node);
void writeData();

int main(int argc, char *argv[]) {

	readData();
	Dijkstra(node(1, 0));
	writeData();

	return 0;
}

void readData() {
	fstream in("dijkstra.in", ios::in);

	long nodeX, nodeY, weight;

	in >> nrVertices >> nrEdges;

	adj.resize(nrVertices+1);
	weights.resize(nrVertices+1);

	for (long i = 1; i <= nrVertices; ++i) {
		weights[i] = INT_MAX;
	}

	for (long i = 1; i <= nrEdges; ++i) {
		in >> nodeX >> nodeY >> weight;
		adj[nodeX].push_back(node(nodeY, weight));
	}

	in.close();
}

void Dijkstra(node startNode) {
	node currentNode;

	weights[startNode.vertex] = 0;
	Q.push(startNode);

	while (!Q.empty()) {
		currentNode = Q.top();
		Q.pop();

		if (currentNode.weight <= weights[currentNode.vertex]) {
			for (list<node>::iterator it = adj[currentNode.vertex].begin(); it != adj[currentNode.vertex].end(); ++it) {
				if (weights[it->vertex] > weights[currentNode.vertex] + it->weight) {
					weights[it->vertex] = weights[currentNode.vertex] + it->weight;
					Q.push(node((it->vertex), weights[it->vertex]));
				}
			}
		}
	}
}

void writeData() {
	fstream out("dijkstra.out", ios::out);

	weights.resize(nrVertices+1);
	for (vector<long>::iterator it = weights.begin()+2; it != weights.end()-1; ++it) {
		if (*it == INT_MAX) {
			out << (*it) << " ";
		}
		else {
			out << "0 ";
		}
	}
	vector<long>::iterator it = weights.end()-1;
	out << *it;

	out.close();
}