#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

struct Vecin{
	int nod;
	short cost;
};

struct GrafOrientat_RLV{
	int n;
	vector< vector<Vecin> > *liste_vecini;
};

void citire(const char nume_fisier[], GrafOrientat_RLV &graf){
	ifstream fin(nume_fisier);
	fin >> graf.n;
	graf.liste_vecini = new vector< vector<Vecin> >(graf.n + 1);
	
	int numar_muchii;
	int ei, ef;
	Vecin vecin;
	fin >> numar_muchii;
	for(int i = 1; i <= numar_muchii; ++i){
		fin >> ei >> ef;
		vecin.nod = ef;
		fin >> vecin.cost;
		(*graf.liste_vecini)[ei].push_back(vecin);
	}
	
	fin.close();
}

vector<int> *costuriMinimeSursa(const unsigned nod_sursa, const GrafOrientat_RLV &graf){
	vector<int> *costuri_minime = new vector<int>(graf.n + 1, INFINIT);
	vector<bool> *in_coada = new vector<bool>(graf.n + 1, false);
	vector<int> *numar_aparitii_in_coada = new vector<int>(graf.n + 1, 0);
	queue<int> *coada = new queue<int>();
	
	(*costuri_minime)[nod_sursa] = 0;
	(*coada).push(nod_sursa);
	(*in_coada)[nod_sursa] = true;
	while(!(*coada).empty()){
		int nod_curent = (*coada).front();
		(*coada).pop();
		(*in_coada)[nod_curent] = false;
		
		Vecin vecin_curent;
		for(int i = 0; i < (*graf.liste_vecini)[nod_curent].size(); ++i){
			vecin_curent = (*graf.liste_vecini)[nod_curent][i];
			int cost_nod_curent = (*costuri_minime)[nod_curent];
			int cost_muchie = vecin_curent.cost;
			int cost_initial = (*costuri_minime)[vecin_curent.nod];
			
			if(cost_nod_curent < INFINIT){
			
				if(cost_nod_curent + cost_muchie < cost_initial){
					(*costuri_minime)[vecin_curent.nod] = cost_nod_curent + cost_muchie;
					
					if(!(*in_coada)[vecin_curent.nod]){
						//verificare ciclu negativ
						if((*numar_aparitii_in_coada)[vecin_curent.nod] > graf.n){
							return NULL;
						}
						(*in_coada)[vecin_curent.nod] = true;
						(*coada).push(vecin_curent.nod);
						++(*numar_aparitii_in_coada)[vecin_curent.nod];
					}
				}
			}
		}
	}
	delete in_coada;
	delete numar_aparitii_in_coada;
	delete coada;
	
	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_RLV graf;
	citire(NUME_FISIER_INTRARE, graf);
	vector<int> *costuri_minime = costuriMinimeSursa(SURSA_COSTURI, graf);
	afisare(NUME_FISIER_IESIRE, costuri_minime);
	
	return 0;
}