#include <fstream>
#include <vector>

using namespace std;

const char NUME_FISIER_INTRARE[] = "bellmanford.in";
const char NUME_FISIER_IESIRE[] = "bellmanford.out";
const int SURSA_COSTURI = 1;
const int INFINIT = 1000000000;

struct Muchie{
	int ei;
	int ef;
	short cost;
};

struct GrafOrientat_RVM{
	int n;
	vector<Muchie> *muchii;
};

void citire(const char nume_fisier[], GrafOrientat_RVM &graf){
	ifstream fin(nume_fisier);
	
	int size; //numarul de muchii;
	fin >> graf.n >> size;
	graf.muchii = new vector<Muchie>(size);
	
	for(int i = 0; i < (*graf.muchii).size(); ++i){
		fin >> (*graf.muchii)[i].ei;
		fin >> (*graf.muchii)[i].ef;
		fin >> (*graf.muchii)[i].cost;
	}
	
	fin.close();
}

vector<int> *costuriMinimeSursa(const int nod_sursa, const GrafOrientat_RVM &graf){
	vector<int> *costuri_minime = new vector<int>(graf.n+1);
	for(int i = 1; i <= graf.n; ++i){
		(*costuri_minime)[i] = INFINIT;
	}
	(*costuri_minime)[nod_sursa] = 0;
	
	//aproximeaza repetat costurile
	for(int i = 1; i <= graf.n; ++i){
		for(int k = 0; k < (*graf.muchii).size(); ++k){
			int cost_pana_aici = (*costuri_minime)[(*graf.muchii)[k].ei];
			int cost_muchie = (*graf.muchii)[k].cost;
			int cost_initial = (*costuri_minime)[(*graf.muchii)[k].ef];
			if(cost_pana_aici + cost_muchie < cost_initial){
				(*costuri_minime)[(*graf.muchii)[k].ef] = cost_pana_aici + cost_muchie;
			}
		}
	}
	
	//verific daca exista cicluri negative
	for(int k = 0; k < (*graf.muchii).size(); ++k){
		int cost_pana_aici = (*costuri_minime)[(*graf.muchii)[k].ei];
		int cost_muchie = (*graf.muchii)[k].cost;
		int cost_initial = (*costuri_minime)[(*graf.muchii)[k].ef];
		if(cost_pana_aici + cost_muchie < cost_initial){
			return NULL;
		}
	}
	
	return costuri_minime;
}

void afisare(const char nume_fisier[], vector<int> *costuri_minime){
	ofstream fout(nume_fisier);
	
	if(costuri_minime == NULL){
		fout << "Ciclu negativ!";
	}else{
		for(int i = 2; i < (*costuri_minime).size(); ++i){
			fout << (*costuri_minime)[i] << " ";
		}
	}
	
	fout.close();
}

int main(int argc, char *argv[]){
	GrafOrientat_RVM graf;
	
	citire(NUME_FISIER_INTRARE, graf);
	vector<int> *vector_costuri_minime = costuriMinimeSursa(SURSA_COSTURI, graf);
	afisare(NUME_FISIER_IESIRE, vector_costuri_minime);
	
	return 0;
}