#include<fstream>
#include<vector>
#include<queue>
#define DIM 50005
#define f first
#define s second
using namespace std;
int n, m, i, x, y, z, nod, vecin, ok;
int d[DIM], ff[DIM], num[DIM];
queue<int> c;
vector< pair<int, int> > v[DIM];
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int main(){
    fin>> n >> m;
    for(i = 1; i <= m; i++){
        fin>> x >> y >> z;
        v[x].push_back( make_pair(y, z) );
    }
    for(i = 2; i <= n; i++){
        d[i] = 1000000000;
    }
    ff[1] = 1;
    c.push(1);
    while(!c.empty()){
        nod = c.front();
        c.pop();
        ff[nod] = 0;
        num[nod]++;
        if(num[nod] == n){
            ok = 1;
            break;
        }
        for(i = 0; i < v[nod].size(); i++){
            vecin = v[nod][i].f;
            if(d[vecin] > d[nod] + v[nod][i].s){
                d[vecin] = d[nod] + v[nod][i].s;
                if(ff[vecin] == 0){
                    ff[vecin] = 1;
                    c.push(vecin);
                }
            }
        }
    }
    if(ok == 1){
        fout<<"Ciclu negativ!";
    }
    else{
        for(i = 2; i <= n; i++){
            fout<< d[i] <<" ";
        }
    }
    return 0;
}