#include <iostream>
#include <fstream>
#include <vector>

#define NMAX 50001
#define INF 123456789
using namespace std;

int N, M;

struct Edge
{
	int src, dest, weight;
};

struct Graph{
	int N, M;
	struct Edge* edge;
};

struct Graph* createGraph(){
	struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
	graph->N = N;
	graph->M = M;

	graph->edge  = (struct Edge*) malloc(sizeof(struct Edge) * M);

	return graph;
}

vector<int> distances(NMAX, INF);
struct Graph* graph;

ofstream g("bellmanford.out");

void bellmanford(){

	for(int i = 1; i <= N - 1; i++){
		for(int j = 0; j < M; j++){
			int src = graph->edge[j].src;
			int dest = graph->edge[j].dest;
			int cost = graph->edge[j].weight;
			if(distances[dest] > distances[src] + cost && distances[src] != INF)
				distances[dest] = distances[src] + cost;
		}
	}

	for(int j = 0; j < M; j++){
		int src = graph->edge[j].src;
		int dest = graph->edge[j].dest;
		int cost = graph->edge[j].weight;
		if(distances[dest] > distances[src] + cost && distances[src] != INF){
			g << "Ciclu negativ!";
			return;
		}
	}

	for(int i = 2; i <= N; i++)
		g << distances[i] << " ";
}
int main(){
	ifstream f("bellmanford.in");
	int a, b, c;
	f >> N >> M;
	graph = createGraph();

	for(int i = 0; i < M; i++){
		f >> a >> b >> c;
		Edge edge;
		edge.src = a;
		edge.dest = b;
		edge.weight = c;
		graph->edge[i] = edge;
	}
	f.close();

	distances[1] = 0;
	bellmanford();

	g.close();

	return 0;
}