#include <fstream>
#include <vector>
#include <queue>
//#include <time.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

//data
vector<pair<int, int>> graph[50001];
priority_queue<pair<int, int>> heap;
int dist[50001];
int vertices, edges;



void input()
{
	//reads the graph from the file
	f >> vertices >> edges;
	for (int i = 1; i <= edges; i++)
	{
		int a, b, weight;
		f >> a >> b >> weight;
		graph[a].push_back({ weight, b });
	}
}

void RELAX(int node1, int dist1, int node2, int dist2, int weight)
{
	///checks if the distance from a to b using the givven wight is better than the existing b distance
	long long bigSum = dist1 + weight;

	if (bigSum < dist2)
	{															//updates only if a lower distance
		dist[node2] = bigSum;							//set the non infinite distance
	}
	else
		return;
}

int bellmanFord()
{
	for (int i = 1; i <= vertices; i++)
		dist[i] = 0x7FFFFFFF;						//'infinity'

	dist[1] = 0;

	heap.push({ 0,1});									//the first node

	for (int step = 1; step < vertices; step++)		
	{

		bool visited[50001] = { 0 };
		visited[1] = true;
		int heapSize = heap.size();

		while (heapSize)
		{
			int nodeId = heap.top().second;
			int nodeDist = -heap.top().first;
			heap.pop();
			heapSize--;

			visited[nodeId] = false;

			for (auto elem : graph[nodeId])
			{
				
				int id = elem.second;
				int val = dist[id];
				int weight = elem.first;

				RELAX(nodeId, dist[nodeId], id, dist[id], weight);

				if (dist[nodeId] + weight < dist[id])
					return 0;

				if (dist[id] != 0x7FFFFFFF && val > dist[id] && !visited[id])
				{
					heap.push({ -dist[id],id });
					visited[id] = true;
				}
			
			}
		}
	}


	
	for (int nodePos = 1; nodePos <= vertices; nodePos++)										//
	{																								//
		for(auto x:graph[nodePos])																	//for each edge
		{

			if (dist[nodePos] + x.first < dist[x.second])
				return 0;
		}
	}
	

	return 1;
	
}










int main()
{
	//clock_t start = clock();

	input();

	int res = bellmanFord();
	if (res == 1)
	{
		for (int i = 2; i <= vertices; i++)
			g << dist[i] << " ";
	}

	else
		g << "Ciclu negativ!";




	f.close();
	g.close();



	//clock_t end = clock();
	//float seconds = (float)(end - start) / CLOCKS_PER_SEC;
	//printf("%f", seconds);
	

	return 0;
}