/*
 * 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;

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)
{
	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 (in_queue[u]) return 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;
	
	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);
		
		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[1] = 0;
	
	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);

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

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