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

#define DEBUG_PRINT 0

namespace bellman_ford_v05
{
	const int MAX_N = 50000;

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

	//pre-declare debug data printer function
	void print_debug_data(string msg, int u, vector<int>& cost_to, vector<char>& in_queue,
			vector<int>& max_update_level, deque<int>& Q);

	bool bellman_ford_bfs(int N, vector<int>* adj_list, vector<int>* cost_list,
			vector<int>& cost_to)
	{
		vector<int> Q;
		//0 - not in queue, 1 - in queue
		vector<char> in_queue;
		//the maximum bfs level where the nodes were updated
		vector<int> max_update_level;
		in_queue.resize(N + 1);
		cost_to.resize(N + 1);
		max_update_level.resize(N + 1);
		fill(in_queue.begin(), in_queue.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);
		in_queue[1] = 1;
		cost_to[1] = 0;

		int total_nodes_in_queue = 0;

		while (!Q.empty())
		{
			// the maximum level is N, 
			// but we allow one more run in order to detect the negative cycles

			//extract one element from the queue
			std::pop_heap(Q.begin(), Q.end(), std::greater<int>{}); //move the minimum to the end
			int u = Q.back();
			Q.pop_back();			
			in_queue[u] = 0;
			
			total_nodes_in_queue++;
			if (total_nodes_in_queue == N + 1) return true; //ciclu negativ
			
#if DEBUG_PRINT
			string msg1 = "Process node " + to_string(u);
			print_debug_data(msg1, u, cost_to, in_queue, max_update_level, Q);
#endif
			//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;
				}

				if (cost_updated && in_queue[v] != 1)
				{
					//cost update if node not already in the queue
					Q.push_back(v);
					std::push_heap(Q.begin(), Q.end(), std::greater<int>{});
					in_queue[v] = 1;
				}
			}

#if DEBUG_PRINT
			string msg2 = "Done processing node " + to_string(u);
			print_debug_data(msg2, u, cost_to, in_queue, max_update_level, Q);
#endif
		}

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

namespace bellman_ford_v05
{
	bool first_time_debug_print = true;

	void print_debug_data(string msg, int u, vector<int>& cost_to, vector<char>& in_queue,
			vector<int>& max_update_level, deque<int>& Q)
	{
		//print the data
		ofstream ofs;

		ofstream::openmode opm = std::ofstream::app;
		if (first_time_debug_print)
		{
			opm = std::ofstream::out;
			first_time_debug_print = false;
		}

		ofs.open("bellmanford_debug.out", opm);

		ofs << msg << endl;

		int N = cost_to.size() - 1;

		ofs << "cost to: ";
		for (int v = 1; v <= N; v++)
			ofs << cost_to[v] << " ";
		ofs << endl;

		ofs << "in queue: ";
		for (int v = 1; v <= N; v++)
			ofs << (int) in_queue[v] << " ";
		ofs << endl;

		ofs << "max update level: ";
		for (int v = 1; v <= N; v++)
			ofs << (int) max_update_level[v] << " ";
		ofs << endl;

		ofs << "Q: ";
		for (auto& v : Q)
			ofs << v << " ";
		ofs << endl << endl;

		ofs.close();
	}
}