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

using namespace std;

int main() 
{
	int nrOfNodes, nrOfEdges;
	int *dist, *prev,*nrOfRelax, 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];
	nrOfRelax = new int[nrOfNodes + 1];
	for (int i = 1; i <= nrOfNodes; i++)
		dist[i]=INT32_MAX,nrOfRelax[i]=prev[i]=0;
	src = 1;
	dist[src] = 0;
	Nodes.push(src);
	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));
	}
	

	while (!Nodes.empty())
	{
		int current = Nodes.front();
		Nodes.pop();
		bool relaxed = false;
		for (pair<int, int>p : adjList[current])
		{
			int y, d;
			y = p.second; d = p.first;
			if (dist[y] > dist[current] + d)
			{
				dist[y] = dist[current] + d;
				prev[y] = current;
				nrOfRelax[current]++;
				Nodes.push(y);
				if(nrOfRelax[current]==nrOfEdges)
				{
					fout << "Ciclu negativ!";
					fout.close();
					fin.close();
					return 0;
				}

				relaxed = true;

			}
			if (relaxed) Nodes.push(current);
		}
	}
/*
	for(int i=1;(i<nrOfNodes) && (!Nodes.empty());i++)
		{
			int x = Nodes.front();
			Nodes.pop();
			bool relaxed;
			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);
			}
			else 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;
}