#include <iostream>
#include <cstdio>
#include <list>
#include <vector>
#include <set>
#include <queue>

#define Inf ((1<<30)-1)

using namespace std;

struct Graph {
	vector<list<pair<unsigned int, int> > > v;
};

Graph* readOrientedGraph() {
	int n, m;
	cin >> n >> m;

	Graph *G = new Graph();
	G->v.assign(n+1, *new list<pair<unsigned int, int> >());

	unsigned int x, y;
	int z;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		G->v[x].push_back(make_pair(y, z));
	}

	return G;
}

Graph* readGraph() {
	int n, m;
	cin >> n >> m;

	Graph *G = new Graph();
	G->v.assign(n + 1, *new list<pair<unsigned int, int> >());

	unsigned int x, y;
	int z;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> z;
		G->v[x].push_back(make_pair(y, z));
		G->v[y].push_back(make_pair(x, z));
	}

	return G;
}

int *d;

void dijkstra(Graph *G, unsigned int startNode) {
	set<pair<int, unsigned int> > st;
	d = new int[G->v.size ()];
	for (unsigned int i = 1; i < G->v.size(); i++)
		d[i] = i == startNode ? 0 : Inf;

	st.insert(make_pair (0, startNode));
	while (!st.empty()) {
		unsigned int node = st.begin()->second;
		//pop
		st.erase(st.begin());

		for (list<pair<unsigned int, int> >::iterator it = G->v[node].begin (); it != G->v[node].end (); it++)
			if (d[it->first] > d[node] + it->second) {				
				set<pair<int, unsigned int> >::iterator nodeIterator = st.find (make_pair (d[it->first], it->first));

				if (nodeIterator != st.end())
					st.erase(nodeIterator);

				d[it->first] = d[node] + it->second;
				st.insert(make_pair(d[it->first], it->first));
				
				//push
				st.insert(make_pair (d[it->first], it->first));
			}
	}
}


bool *isInQ;
unsigned int *cnt;
bool bellman_ford(Graph *G, int startNode) {
	queue<unsigned int> q;

	d = new int[G->v.size()];
	isInQ = new bool[G->v.size()];
	cnt = new unsigned int[G->v.size()];

	for (unsigned int i = 1; i < G->v.size(); i++)
		d[i] = i == startNode ? 0 : Inf,
		isInQ[i] = false,
		cnt[i] = 0;

	q.push(startNode);
	isInQ[startNode] = true;

	while (!q.empty ()) {
		unsigned int node = q.front();
		q.pop();
		isInQ[node] = false;

		for (list<pair<unsigned int, int> >::iterator it = G->v[node].begin(); it != G->v[node].end(); it++)
			if (d[it->first] > d[node] + it->second) {
				d[it->first] = d[node] + it->second;

				if (!isInQ[it->first]) {
					isInQ[it->first] = true;

					cnt[it->first]++;
					if (cnt[it->first] > G->v.size() - 1)
						return false;
					q.push(it->first);
				}
			}
	}
	
	return true;
}

int main() {
	freopen("bellmanford.in", "rt", stdin);
	freopen("bellmanford.out", "wt", stdout);

	unsigned int startingNode = 1;
	Graph *G = readOrientedGraph();

	if (bellman_ford(G, startingNode)) {
		for (unsigned int i = 1; i <= G->v.size() - 1; i++)
			if (i != startingNode)
				cout << (Inf != d[i] ? d[i] : 0) << ' ';
	}
	else
		cout << "Ciclu negativ!";


	return 0;
}