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

using namespace std;

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

//data
vector<pair<int, int>> graph[50001];
queue<pair<int, int>> heap;
int dist[50001];
int vertices, edges;
int times[50001] = { 0 };



void input()
{
	//reads the graph from the file
	FILE* file = fopen("bellmanford.in", "r");

	fscanf(file, "%d %d", &vertices, &edges);

	for (int i = 1; i <= edges; i++)
	{
		int a, b, weight;
		fscanf(file, "%d %d %d", &a, &b, &weight);
		graph[a].push_back({ weight, b });
	}
	fclose(file);
	return;

	
}

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, times[i] = 0;				//'infinity'

	dist[1] = 0;
	times[1] = 1;

	heap.push({ 0,1});									//the first node
	
	while (!heap.empty())
	{
		int nodeId = heap.front().second;
		int nodeDist = -heap.front().first;
		heap.pop();


		for (auto elem : graph[nodeId])
		{

			int id = elem.second;
			int val = dist[id];
			int weight = elem.first;


			if (times[id] == vertices - 1)
				return 0;

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


			if (val > dist[id])
			{
				times[id]++;
				heap.push({ -dist[id],id });
			}

		}
	}


	
	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;
}