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

const int DMax = 50005;
const int inf = (1 << 30);

std::vector<std::pair<int, int>> G[DMax];
int distance[DMax];
int N, M;

std::ifstream fin("bellmanford.in");
std::ofstream fout("bellmanford.out");


void citeste() {

	fin >> N >> M;
	for (int i = 1; i <= M; i++) {
		int x, y, c;
		fin >> x >> y >> c;
		G[x].push_back(std::make_pair(y, c));
	}
}

void initalizare(int sursa) {
	for (int i = 1; i <= N; i++)
		distance[i] = inf;
	distance[sursa] = 0;
}

void relax(int u, int v,int w) {
	
	if (distance[v] > distance[u] + w)
	      distance[v] = distance[u] + w;
}


bool BellmannFord(int sursa) {

	initalizare(sursa);

 
	for (int i = 1; i <= N; i++)
		for (unsigned int j = 0; j < G[i].size(); j++) {
			int u = i;
			int v = G[i][j].first;
			int w = G[i][j].second;
			relax(u, v, w);
		}


	for (int i = 1; i <= N; i++)
		for (unsigned int j = 0; j < G[i].size(); j++) {
			int u = i;
			int v = G[i][j].first;
			int w = G[i][j].second;
			if (distance[v] > distance[u] + w)
				return true;
		}
	return false;
}



int main() {

	citeste();
	bool rasp=BellmannFord(1);
	if (rasp) std::cout << "Negativ";
	else {
		for (int i = 2; i <= N; i++)
			fout << distance[i] << " ";
	}

	return 0;
}