/*
 * find_negative_cicles.cpp
 *
 *  Created on: May 1, 2015
 *      Author: Marius
 */

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

bool debug_print_enabled = false;
bool first_time_debug_print = true;

bool dfs_negative_cycle(int node, int parent_node, int cost_parent_to_node, int N, vector<int>* adj_list, vector<int>* cost_list,
		vector<int>& nodes_hit, vector<int>& Q, int& q_end_index, vector<int>& pos_in_Q, vector<int>& partial_sums)
{
	//new node, add it in the queue
	q_end_index++;
	Q[q_end_index] = node;
	pos_in_Q[node] = q_end_index;
	nodes_hit[node] = 1;
	//the parent node, if not the first node
	if (parent_node != -1)
	{
		//update the sums
		partial_sums[q_end_index] += cost_parent_to_node + partial_sums[q_end_index - 1];
	}

	bool found_negative_cycle = false;
	//parse the adjacency list of the current node
	int adj_list_size = adj_list[node].size();
	for (int j = 0; j < adj_list_size; j++)
	{
		int v = adj_list[node][j];
		int cost_node_v = cost_list[node][j];
		//node visited for the first time
		if (!nodes_hit[v])
		{
			//simply put the node in the queue
			found_negative_cycle =
					dfs_negative_cycle(v, node, cost_node_v, N, adj_list, cost_list, nodes_hit,
							Q, q_end_index, pos_in_Q, partial_sums);
		}
		else if (pos_in_Q[v] != -1) //we have seen this node so far and it is also in the current queue
		{
			//node visited for the second time
			//yes, there is a cycle
			//check if it is a negative cycle
			//simply check the partial sums
			int cycle_sum = partial_sums[q_end_index] - partial_sums[pos_in_Q[v]] + cost_node_v;
			if (cycle_sum < 0) found_negative_cycle = true;

			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 << "cycle sum: " << cycle_sum << ", nodes: ";
				for (int k = pos_in_Q[v]; k <= q_end_index; k++) ofs << Q[k] << " ";
				ofs << v << " " << endl;
				ofs.close();
			}
		}
		//do not process the rest of the nodes if we have a negative cycle
		if (found_negative_cycle) break;		
	}

	//I am done with the current node
	pos_in_Q[node] = -1; //node no longer in the queue
	//update the partial sums because the node was removed
	if (parent_node != -1) {
		partial_sums[q_end_index] -= cost_parent_to_node + partial_sums[q_end_index - 1];
	}
	//pop the node from the queue
	q_end_index--;
	

	return found_negative_cycle;
}

/// The method finds a negative cycle in the graph.
/// Returns true if a negative cycle is found, false otherwise.
bool contains_negative_cycles(int N, vector<int>* adj_list, vector<int>* cost_list)
{

	vector<int> Q;
	vector<int> pos_in_Q, partial_sums;
	vector<int> nodes_hit;
	Q.resize(N+1);
	int q_end_index = 0;
	pos_in_Q.resize(N + 1);
	partial_sums.resize(N + 1);
	nodes_hit.resize(N + 1);

	std::fill(Q.begin(), Q.end(), 0);
	std::fill(pos_in_Q.begin(), pos_in_Q.end(), -1);
	std::fill(partial_sums.begin(), partial_sums.end(), 0);
	std::fill(nodes_hit.begin(), nodes_hit.end(), 0);

	bool found_negative_cycle = false;
	for (int node = 1; node <= N; node++)
	{
		if (!nodes_hit[node])
			found_negative_cycle = dfs_negative_cycle(node, -1, 0, N, adj_list, cost_list, nodes_hit, Q, q_end_index, pos_in_Q, partial_sums);
		if (found_negative_cycle) break;
	}

	return found_negative_cycle;
}

void bellman_ford(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; 
	node_status.resize(N + 1);
	cost_to.resize(N + 1);
	fill(node_status.begin(), node_status.end(), 0);
	fill(cost_to.begin(), cost_to.end(), std::numeric_limits<int>::max());
	
	//add the root node in the queue
	Q.push_back(1);
	node_status[1] = 1; 
	cost_to[1] = 0;
	
	while (!Q.empty())
	{
		//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;
			}
			
			if (cost_updated && node_status[v] != 1) {
				//cost update and node not already in the queue
				Q.push_back(v);
				node_status[v] = 1;
			}			
		}
	}
}

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

	const int MAX_N = 50000;

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

	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);
	string negative_cycle_msg = "Ciclu negativ!";

	std::vector<int> cost_to;
	if (!has_negative_cycles) bellman_ford(N, adj_list, cost_list, cost_to);
	
	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 << cost_to[i] << " ";
	}
	ofs.close();

	return 0;
}