#include<fstream>
#include<set>
#include<limits>
#include<list>
#include<queue>
//#include<algorithm>

using namespace std;

int main() 
{
	int nrOfNodes, nrOfEdges;
	int *dist, *prev, src;
	list<pair<int, int>>*adjList;
	queue<int>Nodes;
	ifstream fin("bellmanford.in");
	ofstream fout("bellmanford.out");
	fin >> nrOfNodes >> nrOfEdges;
		dist = new int[nrOfNodes + 1];
	prev = new int[nrOfNodes + 1];
	for (int i = 1; i <= nrOfNodes; i++)
		Nodes.push(i),dist[i]=INT32_MAX,prev[i]=NULL;
	src = 1;
	dist[src] = 0;

	adjList = new list<pair<int, int>>[nrOfNodes + 1];

	for (int i = 0; i < nrOfEdges; i++)
	{
		int x, y, d;
		fin >> x >> y >> d;
		adjList[x].push_back(make_pair(d, y));
	}

	for(int i=0;i<nrOfNodes && !Nodes.empty();i++)
		{
			int x = Nodes.front();
			Nodes.pop();
			bool relaxed=true;
			if (dist[x] != INT32_MAX)
			{
				relaxed = false;
				for (pair<int, int>p : adjList[x])
				{
					int y, d;
					y = p.second; d = p.first;
					if (dist[y] > dist[x] + d)
					{
						dist[y] = dist[x] + d;
						prev[y] = x;
						relaxed = true;

					}
				}
			}
			if (relaxed)
				Nodes.push(x);

		}


	for(int i=1;i<=nrOfNodes;i++)
		for(pair<int,int>p:adjList[i])
			if (dist[i] + p.first < dist[p.second])
			{
				fout << "Ciclu negativ!";
				fout.close();
				fin.close();
				return 0;
			}

	for (int i = 2; i <= nrOfNodes; i++)
		if (dist[i] == INT32_MAX)
			fout << 0 << " ";
		else fout << dist[i] << " ";

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