#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define MAX_N 50000
#define INF 10001
struct muchie{
    long x, y, cost;
};
 
vector<muchie> vec; // vector de muchii
long drum[MAX_N]; // vector de drumuri
long n, m, viz[MAX_N];
 
void bellmanford(int nod);
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
 
int main()
{
 
 
    fin >> n >> m;
 
    for(long i=1; i<=n; i++){
        drum[i] = INF;
    }
 
 
    for(long i=0; i<m; i++){
        muchie m; fin >> m.x >> m.y >> m.cost;
        vec.push_back(m);
        if(m.x == 1)
            drum[m.y] = m.cost;
    }
 
 
    bellmanford(1);
    return 0;
}
 
 
void bellmanford(int nod){
    bool ok;
	long contor = 0;
    do{
		contor++;
        ok = false;
        for(size_t i=0; i< vec.size(); i++){
            if(drum[vec[i].y] > drum[vec[i].x] + vec[i].cost){
                drum[vec[i].y] = drum[vec[i].x] + vec[i].cost;
                viz[vec[i].y] ++;
                ok = true;
            }
        }
    }while(ok && contor <n);
	
	if(contor == n){
		fout << "Ciclu negativ!";
	}else{
        for(long i=2; i<=n; i++){
          fout << drum[i] << " ";
        }
	}
}