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

#define input_file "bellmanford.in"
#define output_file "bellmanford.out"

const int INF = ~(1 << 31);

using namespace std;

int n, m;
vector< vector<pair<int,int> > >g;
vector< int > color, in_queue, d;

void read_graph()
{
	int u, v, cost;
	ifstream in(input_file);
	in >> n >> m;
	g.resize(n);
	for(int i = 0; i < m; i++)
	{
		in >> u >> v >> cost;
		g[u-1].push_back( make_pair(v-1, cost) );
	}
	in.close();
}

bool bellmanford(int source)
{
	color.assign(n, 0);
	in_queue.assign(n, 0);
	color[source] = 1;
	d.assign(n, INF);
	
	d[source] = 0;
	color[source] = 1;
	queue<int> Q;
	Q.push(source);
	while( !Q.empty() )
	{
		int u = Q.front();
		for(int i = 0; i < (int) g[u].size(); i++)
		{
			int v = g[u][i].first;
			int cost = g[u][i].second;
			if( d[v] > d[u] + cost )
			{
				d[v] = d[u] + cost;
				if( ++in_queue[v] > n ) return false;
				if( color[v] == 0 )
					Q.push(v), color[v] = 1;
			}
		}
		Q.pop(); 
		color[u] = 0;
	}
	return true;
}

void print_sol(bool ok)
{
	ofstream out(output_file);
	if(!ok) 
		out << "Ciclu negativ!";
	else
		for(int i = 0; i < n; i++)
			out << d[i] << " ";
	out.close();
}

int main()
{
	read_graph();
	print_sol( bellmanford(0) );
	return 0;
}