#include <iostream>
using namespace std;
#include <string>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <limits>

namespace bellman_ford_v05
{
	const int MAX_N = 50000;

	vector<int> adj_list[MAX_N + 1];
	vector<int> cost_list[MAX_N + 1];

	bool bellman_ford_bfs(int N, vector<int>* adj_list, vector<int>* cost_list,
			vector<int>& cost_to)
	{
		deque<int> Q;
		//0 - not in queue, 1 - in queue
		vector<int> node_status;
		//the maximum bfs level where the nodes were updated
		vector<int> max_update_level;
		node_status.resize(N + 1);
		cost_to.resize(N + 1);
		max_update_level.resize(N + 1);
		fill(node_status.begin(), node_status.end(), 0);
		fill(cost_to.begin(), cost_to.end(), std::numeric_limits<int>::max());
		fill(max_update_level.begin(), max_update_level.end(), 0);
		
		//add the root node in the queue
		Q.push_back(1);
		node_status[1] = 1;
		cost_to[1] = 0;
		max_update_level[1] = 1;
		
		int max_level = 1;

		while (!Q.empty() && max_level <= N)
		{
			//extract one element from the queue
			int u = Q.front();
			Q.pop_front();
			node_status[u] = 0;

			//process the adjacency nodes
			int adj_list_size = adj_list[u].size();
			for (int j = 0; j < adj_list_size; j++)
			{
				int v = adj_list[u][j];
				int cost_uv = cost_list[u][j];
				bool cost_updated = false;
				if (cost_to[v] > cost_to[u] + cost_uv)
				{
					cost_to[v] = cost_to[u] + cost_uv;
					cost_updated = true;		
					//update the maximum update level
					max_update_level[v] = max(max_update_level[v], max_update_level[u] + 1);
					max_level = max(max_level, max_update_level[v]);
				}

				if (cost_updated && node_status[v] != 1)
				{
					//cost update if node not already in the queue
					Q.push_back(v);
					node_status[v] = 1;
				}
			}
		}

		//check for negative cycles
		for (int u = 1; u <= N; u++)
		{
			//process the adjacency nodes
			int adj_list_size = adj_list[u].size();
			for (int j = 0; j < adj_list_size; j++)
			{
				int v = adj_list[u][j];
				int cost_uv = cost_list[u][j];
				if (cost_to[v] > cost_to[u] + cost_uv) return true; //we have a negative cycle
			}
		}

		return false; //no negative cycle
	}
}

//int bellman_ford_main_v01_wrong_cycles()
int main()
{
	using namespace bellman_ford_v05;

	string in_file = "bellmanford.in";
	string out_file = "bellmanford.out";

	int N, M;

	ifstream ifs;
	ifs.open(in_file.c_str());
	if (!ifs.is_open())
	{
		cout << "Input file not found" << endl;
		return -1;
	}
	ifs >> N >> M;
	for (int j = 1; j <= M; j++)
	{
		int v1, v2, c12;
		ifs >> v1 >> v2 >> c12;
		//append in the adjacency list of the node v1
		adj_list[v1].push_back(v2);
		cost_list[v1].push_back(c12);
	}
	ifs.close();

	//bool has_negative_cycles = contains_negative_cycles(N, adj_list, cost_list);

	std::vector<int> cost_to;
	bool has_negative_cycles = bellman_ford_bfs(N, adj_list, cost_list, cost_to);

	ofstream ofs;
	ofs.open(out_file.c_str());
	if (has_negative_cycles)
		ofs << "Ciclu negativ!";
	else
		for (int i = 2; i <= N; i++)
			ofs << cost_to[i] << " ";
	ofs.close();

	return 0;
}