#include <fstream>
#include <vector>
#include <climits> 

class Vertex {
public:
	int dist;

	Vertex() {}
	Vertex(int dist) : dist(dist) {}
	Vertex(const Vertex& copy) {
		this->dist = copy.dist;
	}
};

class Edge {
public:
	int start, stop, weight;
	Edge() {}
	Edge(int start, int stop, int weight) : start(start), stop(stop), weight(weight){}
	Edge(const Edge& copy) {
		this->start = copy.start;
		this->stop = copy.stop;
		this->weight = copy.weight;
	}
};

class Data {
public:
	int n, m;
	std::vector<Vertex> vertices;
	std::vector<Edge> edges;
	int negCycle;

	void read() {
		std::ifstream f("grader_test1.in");
		int start, stop, weight;
		f >> n >> m;
		for (int i = 0; i < m; ++i) {
			f >> start >> stop >> weight;
			Edge edge(start, stop, weight);
			edges.push_back(edge);
		}
		for (int i = 0; i <= n; ++i) {
			Vertex vertex(INT_MAX);
			vertices.push_back(vertex);
		}
	}

	void write() {
		std::ofstream g("bellmanford.out");
		if (negCycle) {
			g << "Ciclu negativ!";
		}
		else {
			for (int i = 2; i <= n; ++i) {
				g << vertices[i].dist << ' ';
			}
		}
	}
};

class Algo {
	Data& data;
public:
	Algo(Data& data) : data(data){}
	void bellmanford() {
		std::vector<Vertex>& vertices = data.vertices;
		vertices[1].dist = 0;

		for (int i = 1; i < vertices.size(); ++i) {
			for (Edge edge : data.edges) {
				if (vertices[edge.start].dist != INT_MAX && vertices[edge.stop].dist >
					vertices[edge.start].dist + edge.weight) {
					vertices[edge.stop].dist =
						vertices[edge.start].dist + edge.weight;
				}
			}
		}
		
		data.negCycle = 0;
		for (Edge edge : data.edges) {
			if (vertices[edge.stop].dist >
				vertices[edge.start].dist + edge.weight) {
				data.negCycle = 1;
				break;
			}
		}
	}
};

int main() {
	Data data;
	data.read();
	Algo algo(data);
	algo.bellmanford();
	data.write();
}