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

using namespace std;

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

struct Edge{
		unsigned short node;
		short cost;
};

const int N_MAX = 5e4;
const int COST_MAX = 1e3;
const int VAL_MAX = N_MAX * COST_MAX;
vector<Edge> edge[N_MAX];
unsigned int dist[N_MAX]{};//dist<<1 = cost-ul minim de ajunge in nod, dist&1 = este nodeul in queue?
unsigned short updates[N_MAX]{};

inline int encode(int value, bool inqueue){
	return (value << 1) + inqueue;
}

inline int decode_value(int code){
	return code >> 1;
}

inline bool decode_inqueue(int code){
	return code & 1;
}

bool BellmanFord(int start, int nodes){
	for(int node = 0; node < nodes; ++node)
		dist[node] = encode(VAL_MAX + 1, false);

	queue<int> q;
	int node = start;

	q.push(node);
	dist[node] = encode(1, true);
	++updates[node];

	while(!q.empty() && updates[node] < nodes){
		node = q.front();

		for(auto neighbour: edge[node])
			if(decode_value(dist[neighbour.node]) > decode_value(dist[node]) + neighbour.cost){
				if(!decode_inqueue(dist[neighbour.node]))
					q.push(neighbour.node);

				dist[neighbour.node] = encode(decode_value(dist[node]) + neighbour.cost, true);
				++updates[neighbour.node];
			}

		dist[node] = encode(decode_value(dist[node]), false);
		q.pop();
	}

	return !q.empty();
}

int main(){
	int nodes, edges, a, b, c;
	fin >> nodes >> edges;
	for(int i = 0; i < edges; ++i){
		fin >> a >> b >> c;
		--a;
		--b;

		edge[a].push_back({b, c});
	}

	if(!BellmanFord(0, nodes)){
		for(int node = 1; node < nodes; ++node)
			fout << decode_value(dist[node]) - 1 << ' ';
		fout.put('\n');
	}else
		fout << "Ciclu negativ!\n";

	fin.close();
	fout.close();
	return 0;
}