#include <fstream>
#include <vector>

using namespace std;
typedef unsigned int uint;

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

class Graph
{
	struct cost
	{
		uint src,dest;
		int weight;
	};
	uint V;
	vector<cost> adj;
public:
	Graph(const uint V);
	void Add_edge(uint x, uint y, int c);
	void Bellmanford(uint start);
};

Graph::Graph(const uint V)
{
	this->V = V;
}

void Graph::Add_edge(uint s, uint d, int w)
{
	adj.push_back({s,d,w});
}

void Graph::Bellmanford(uint start)
{
	const int oo = (1 << 31) - 1;
	vector<int> dist(V + 1, oo);
	dist[start] = 0;

	for (size_t i = 1; i < V; ++i)
	{
		for (auto &j : adj)
		{
			if (dist[j.src] != oo)
				dist[j.dest] = min(dist[j.dest], dist[j.src] + j.weight);
		}
	}

	for (auto &i : adj)
    {
        if (dist[i.src] + i.weight < dist[i.dest])
        {
            fout << "Ciclu negativ!";
            return;
        }
    }

	for (size_t i = 2; i <= V; ++i)
		fout << dist[i] << ' ';
}

int main()
{
	uint n,m;
	fin >> n >> m;

	Graph G(n);

	for (size_t x,y,c,i = 0; i < m; ++i)
	{
		fin >> x >> y >> c;
		G.Add_edge(x,y,c);
	}

	G.Bellmanford(1);
}