/*
 * 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
{
	const int MAX_N = 5000;

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

	vector<Edge> edges;
	int dist[MAX_N + 1];
}

bool bellman_ford(vector<bellmanford::Edge>& edges, int N, int* dist)
{
	using bellmanford::Edge;

	fill(dist, dist + N + 1, numeric_limits<int>::max());
	//intialize the source
	dist[1] = 0;
	
	for (int i = 1; i < N; i++)
		for (auto& e : edges)
			if (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;

	edges.resize(M);
	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;
}