#include <fstream>
#include <vector>
#include <cstring>
#define MAX_NODES 50000
#define INF 0x7f7f7f7f
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector<pair<int, int>> directedGraph[MAX_NODES + 1];
int distances[MAX_NODES + 1];

// Let L be the list of all edges.
// This algorithm relaxes each edge which belongs to L, |V| - 1 times, where |V| = number of vertices.
// Our list of edges is: vector<pair<int, int>> directedGraph[MAX_NODES + 1];
void bellmanFord(int startNode, int nrNodes) {
	memset(distances, INF, sizeof distances);
	distances[startNode] = 0;
	for (int time = 1; time < nrNodes; ++time) {
		for (int node = 1; node <= nrNodes; ++node) {
			for (pair<int, int> neighbour : directedGraph[node]) {
				distances[neighbour.first] = min(distances[neighbour.first], distances[node] + neighbour.second);
			}
		}
	}
	// detect if there is a negative weight cycle
	// if there is not, then it means that the relaxation process doe not take 
	for (int node = 1; node <= nrNodes; ++node) {
		for (pair<int, int> neighbour : directedGraph[node]) {
			if (distances[node] + neighbour.second < distances[neighbour.first]) {
				fout << "Ciclu negativ!";
				return;
			}
		}
	}
	for (int node = 2; node <= nrNodes; ++node) {
		fout << distances[node] << ' ';
	}
}

int main() {
	int nrNodes, nrEdges;
	fin >> nrNodes >> nrEdges;
	for (int edge = 0; edge < nrEdges; ++edge) {
		int sourceNode, destinationNode, edgeCost;
		fin >> sourceNode >> destinationNode >> edgeCost;
		directedGraph[sourceNode].push_back({ destinationNode, edgeCost });
	}
	bellmanFord(1, nrNodes);
	return 0;
}