#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_s(&file, "bellmanford.in", "r");

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

	for (int i = 1; i <= edges; i++)
	{
		int a, b, weight;
		fscanf_s(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] = (int)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

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

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

		while (heapSize)
		{
			int nodeId = heap.front().second;
			int nodeDist = -heap.front().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 (times[id] == vertices - 1 )
					return 0;

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

			}
		}
	}

	for (int i = 1; i <= vertices; i++)
	{
		for (auto x : graph[i])
		{
			if (dist[i] + 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;
}