#include <iostream>
#include <fstream>
#include <climits>
#include <queue>

using namespace std;

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

int n, m;
vector<vector< pair<int, int> > > graph;

int main()
{
	vector<int> in_queue;
	vector<int> dist;
	vector<int> counter_queue;
	queue<int> q;
	bool negative_cycle = false;
	int x, y, c;
	fin>>n>>m;
	graph.resize(n+1);
	dist.resize(n+1, INT_MAX);
	in_queue.resize(n+1, false);
	counter_queue.resize(n+1, 0);
	for (int i = 1; i <= m; ++i)
	{
		fin>>x>>y>>c;
		graph[x].push_back(make_pair(y,c));
	}
	q.push(1);
	dist[1] = 0;
	while (!q.empty() && !negative_cycle)
	{
		int node = q.front();
		q.pop();
		in_queue[node] = false;
		for (int i = 0; i < graph[node].size(); ++i)
		{
			//cout<<dist[graph[node][i].first]<<" "<<dist[node]<<" "<<graph[node][i].second<<endl;
			if (dist[graph[node][i].first] > dist[node] + graph[node][i].second)
			{
			//	cout<<"modificat"<<endl;
				dist[graph[node][i].first] = dist[node] + graph[node][i].second;
				if (!in_queue[graph[node][i].first] )
				{
					if (counter_queue[graph[node][i].first] > n)
					{
						negative_cycle = true;
						break;
					}
					counter_queue[graph[node][i].first] ++;
					q.push(graph[node][i].first);
					in_queue[graph[node][i].first] = true;	
				}
			}
		}
	}
	//detect negative cycle
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < graph[i].size(); j++)
		{
			if (dist[graph[i][j].first] > dist[i] + graph[i][j].second)
			{
				fout << "Ciclu negativ!\n";
				return 0;
			}
		}
	}
	for (int i = 2; i <= n; ++i)
		fout<<dist[i]<<" ";
	return 0;
}