#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <climits>
using namespace std;

#define NDEBUG

#ifdef NDEBUG
#define dbg	0 && (*((ostream *) 0))
#else
#define dbg clog
#endif

/**
 *	More like a "half" edge.
 */
class Edge
{
	public:
		Edge(long destNode, long edgeCost = 1)
			:	dest(destNode), cost(edgeCost), next(0)
		{}
	
	public:
		Edge * next;
		long dest, cost;
};

/**
 *	Useful interface for an adjacency list.
 */
class AdjacencyList
{
	public:
		AdjacencyList(long nodes)
			:	numNodes(nodes)
		{
			list.resize(nodes + 1, NULL);
		}
		
		~AdjacencyList()
		{
			for(long i = 0; i < list.size(); i++)
			{
				if(list[i])
				{
					Edge * current = list[i];
					while(current)
					{
						Edge * deleted = current;
						current = current->next;
						
						delete deleted;
					}
				}
			}
		}
		
	public:
		void insertEdge(long src, long dest, long cost)
		{
			if(!list[src])
			{
				list[src] = new Edge(dest, cost);
			}
			else
			{
				Edge * e = new Edge(dest, cost);
				e->next = list[src];
				list[src] = e;
			}
		}
		
		Edge * getEdges(long node) { return list[node]; }
		
		void print()
		{
			for(int i = 0; i < list.size(); i++)
			{
				if(list[i])
				{
					Edge * e = list[i];
					while(e)
					{
						cout << "(" << i << ", " << e->dest << ") = " << e->cost << endl;
						e = e->next;
					}
				}
			}
		}
		
	private:
		std::vector<Edge *> list;
		long numNodes;
};

/**
 *	Takes in an adjacency list of a graph G and runs the Bellman Ford algorithm
 *	on it, determining the shortest paths from the source node to all the other
 *	nodes, and if the graph G has negative weight cycles, in which case those
 *	paths are invalid.
 */
class BellmanFord
{
	public:
		BellmanFord(AdjacencyList& adjacencyList, long nVertices, long nEdges, long sourceNode)
			:	numVertices(nVertices), numEdges(nEdges), sourceNode(sourceNode), 
				adjList(adjacencyList), negativeCycles(false)
		{
			distance.resize(nVertices + 1, LONG_MAX);
			updates.resize(nVertices + 1, 0);
			inQueue.resize(nVertices + 1, false);
		}
		
	public:
		void execute()
		{
			bf(sourceNode);
		}
		
		void bf(long start)
		{
			std::list<long> queue;
			queue.push_back(start);
			inQueue[start] = true;
			distance[start] = 0;
			
			long long steps = 0, maxSteps = numVertices;
			maxSteps *= numEdges;
			
			while(!negativeCycles && !queue.empty() && steps <= maxSteps)
			{
				steps++;
				
				long current = queue.front();
				inQueue[current] = false;
				queue.pop_front();
				
				Edge * outEdge = adjList.getEdges(current);
				
				while(outEdge)
				{
					long src = current;
					long dest = outEdge->dest;
					long cost = outEdge->cost;
					
					if(distance[src] != LONG_MAX)
					{
						if(distance[dest] > distance[src] + cost)
						{
							distance[dest] = distance[src] + cost;
							
							if(!inQueue[dest])
							{
								updates[dest]++;
								if(updates[dest] > numVertices)
								{
									negativeCycles = true;
									break;
								}
									
								inQueue[dest] = true;
								queue.push_back(dest);
							}
						}
					}
					outEdge = outEdge->next;
				}
			}
		}
		
		
		const std::vector<long>& getDistances() const { return distance; }
		bool hasNegativeCycles() const { return negativeCycles; }
		
	private:
		long numVertices, numEdges;
		long sourceNode;
		AdjacencyList& adjList;
		std::vector<long> distance, updates;
		std::vector<bool> inQueue;
		bool negativeCycles;
};

int main(int argc, char * argv[]) 
{
	
	const char * inFile = "bellmanford.in";
	const char * outFile = "bellmanford.out";
	
	ifstream fin(inFile);
	
	#ifndef NDEBUG
		if(!fin || !fout) 
		{
			cerr << "Error opening one of \"" << inFile << "\" or \"" << outFile << "\"" << endl;
			return -1;
		}
	#endif
	
	/**
	 *	Read the data in.
	 *	The input graph is directed.
	 */
	long numNodes, numEdges;
	fin >> numNodes >> numEdges;
	
	AdjacencyList adjList(numNodes);
	
	long x, y, cost;
	for(long i = 0; i < numEdges; i++)
	{
		fin >> x;
		fin >> y;
		fin >> cost;
		
		//cout << "(" << x << ", " << y << ") = " << cost << endl;
		adjList.insertEdge(x, y, cost);
	}
	
	//adjList.print();
	
	fin.close();
	
	/**
	 *	Solve the problem.
	 */
	long sourceNode = 1;
	BellmanFord bf(adjList, numNodes, numEdges, sourceNode);
	bf.execute();
	
	
	/**
	 *	Output the answer.
	 */
	ofstream fout(outFile);

	if(bf.hasNegativeCycles())
	{
		fout << "Ciclu negativ!";
	}
	else
	{
		/**
		 *	Write out the distance if there were no negative cycles.
		 */
		const std::vector<long>& distance = bf.getDistances();
		for(long i = 2; i <= numNodes; i++)
		{
			fout << distance[i] << " ";
		}
	}
	
	fout.close();

	return 0;
}