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

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

namespace bellmanford
{
	struct Edge
	{
		int u, v, w;
	};
}

bool bellman_ford(vector<bellmanford::Edge>& edges, int N, vector<int>& dist)
{
	using bellmanford::Edge;
	int max_int = numeric_limits<int>::max();
	fill(dist.begin(), dist.end(), max_int);
	//initialize the source
	dist[1] = 0;
	
	for (int i = 1; i < N; i++)
		for (auto& e : edges)
			if (dist[e.u] != max_int && dist[e.u] + e.w < dist[e.v]) dist[e.v] = dist[e.u] + e.w;

	//check for negative cycles
	bool has_negative_cycles = false;
	for (auto& e : edges)
		if (dist[e.u] + e.w < dist[e.v])
		{
			has_negative_cycles = true;
			break;
		}

	return has_negative_cycles;
}

int main()
{
	using namespace bellmanford;

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

	int N, M;

	ifstream ifs(in_file.c_str());
	if (!ifs.is_open())
	{
		cout << "Input file not found" << endl;
		return 1;
	}
	ifs >> N >> M;

	vector<Edge> edges;
	vector<int> dist;
	edges.resize(M);
	dist.resize(N + 1);
	
	for (int i = 0; i < M; i++)
	{
		Edge e;
		ifs >> e.u >> e.v >> e.w;
		edges[i] = e;
	}
	ifs.close();

	bool has_negative_cycles = bellman_ford(edges, N, dist);
	ofstream ofs(out_file.c_str());
	if (has_negative_cycles)
		ofs << "Ciclu negativ!";
	else
		for (int i = 2; i <= N; i++)
			ofs << dist[i] << " ";

	return 0;
}