/*
 * e_047_bellman_ford.cpp
 *
 *  Created on: May 9, 2015
 *      Author: Marius
 */

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

#define DEBUG_PRINT 0

namespace bellman_ford
{
	bool debug_print_enabled = true;
	bool first_time_debug_print = true;
}

void print_debug_data_if_enabled(string msg, int u, vector<int>& best_1_cost,
		vector<char>& in_queue, vector<int>& Q)
{
	using namespace bellman_ford;

	//print the queue
	if (debug_print_enabled)
	{
		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 = best_1_cost.size() - 1;

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

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

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

		ofs.close();
	}
}

bool bellman_ford_dfs(vector<int>* adj_list, vector<int>* cost_list, vector<int>& best_1_cost,
		vector<char>& in_queue, int u, int path_to_parent_to_u_cost, vector<int>& Q)
{

	if (path_to_parent_to_u_cost >= best_1_cost[u]) return false;
	//otherwise
	//new better cost
	//check if the node ware already in the current queue of processed nodes. If so, there is a
	//negative cycle since we also have a better cost than the previous one
#if DEBUG_PRINT
	string msg1 = "Node " + to_string(u) + string(": better cost ");
	print_debug_data_if_enabled(msg1, u, best_1_cost, in_queue, Q);
#endif
	
	bool found_negative_cycle = false;
	if (in_queue[u]) found_negative_cycle = true;
	
	//otherwise, put the node in queue, parse the adjacency list and further call the dfs routine
	best_1_cost[u] = path_to_parent_to_u_cost; //save the enhanced cost
	in_queue[u] = 1;

#if DEBUG_PRINT
	Q.push_back(u);
	string msg2 = "Node " + to_string(u) + string(": updated ");
	if (found_negative_cycle) msg2 = "Found negative_cycle, " + msg2;
	print_debug_data_if_enabled(msg2, u, best_1_cost, in_queue, Q);
#endif
	
	//late return in order to see the updated cost for the cycle
	if (found_negative_cycle) return true;
	
	int adj_list_size_u = adj_list[u].size();
	for (int i = 0; i < adj_list_size_u; i++)
	{
		int v = adj_list[u][i];
		int cost_u_v = cost_list[u][i];
		int path_to_u_to_v_cost = path_to_parent_to_u_cost + cost_u_v;
		bool found_negative_cycle_v = bellman_ford_dfs(adj_list, cost_list, best_1_cost, in_queue,
				v, path_to_u_to_v_cost, Q);

		if (found_negative_cycle_v) return true; // return if a negative cycle was found
	}

	//done with the current node, remove it from the queue
	in_queue[u] = 0;
	
#if DEBUG_PRINT
	int u_ = Q.back();
	Q.pop_back();
	
	string msg3 = "Node " + to_string(u_) + string(": popped from the queue ");
	print_debug_data_if_enabled(msg3, u, best_1_cost, in_queue, Q);
#endif
	
	return false;
}

//int bellman_ford_main()
int main()
{
	string in_file = "bellmanford.in";
	string out_file = "bellmanford.out";

	const int MAX_N = 50000;
	int N, M;

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

	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();

	vector<int> best_1_cost;
	vector<char> in_queue;
	best_1_cost.resize(N + 1);
	in_queue.resize(N + 1);

	std::fill(best_1_cost.begin(), best_1_cost.end(), std::numeric_limits<int>::max());
	std::fill(in_queue.begin(), in_queue.end(), 0);

	vector<int> Q;

	bool has_negative_cycles = bellman_ford_dfs(adj_list, cost_list, best_1_cost, in_queue, 1, 0,
			Q);

	string negative_cycle_msg = "Ciclu negativ!";
	ofstream ofs;
	ofs.open(out_file.c_str());

	if (has_negative_cycles)
	{
		ofs << negative_cycle_msg;
	}
	else
	{
		for (int i = 2; i <= N; i++)
			ofs << best_1_cost[i] << " ";
	}
	ofs.close();

	return 0;
}