#include <fstream>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int N = 50005, M = 1000000000;
int d[N],poz[N],h[N];
struct nod{
    int nr,cost;
    nod *urm;
}*v[N];
void adaug(int x, int y, int z){
    nod *nou = new nod;
    nou->nr = y;
    nou->cost = z;
    nou->urm = v[x];
    v[x] = nou;
}
void cobor(int t, int l){
    int f;
    while(t <= l){
        f = t;
        if(t*2 <= l){
            f = t*2;
            if(f+1 <=l && d[h[f+1]] < d[h[f]])
                f++;
            if(d[h[t]] > d[h[f]]){
                poz[h[t]] = f;
                poz[h[f]] = t;
                swap(h[f],h[t]);
                t = f;
            }
            else
                return ;
        }
        else
            return ;
    }
}
void urc(int f){
    int t;
    while(f > 1){
        t = f/2;
        if(d[h[t]] > d[h[f]]){
            poz[h[f]] = t;
            poz[h[t]] = f;
            swap(h[f],h[t]);
            f = t;
        }
        else
            f = 1;
    }
}
void bell(int ns, int n){
    int l = 0, rad, c, val;
    nod *nou = new nod;
    for(int i=1;i<=n;i++)
        d[i] = M;
    d[ns] = 0;
    poz[ns] = 1;
    h[++l] = ns;
    while(l){
        rad = h[1];
        swap(h[1],h[l--]);
        poz[h[1]] = 1;
        poz[rad] = 0;
        cobor(1,l);
        nou = v[rad];
        while(nou){
            c = nou->cost;
            val = nou->nr;
            if(d[val] > d[rad] + c){
                d[val] = d[rad] + c;
                if(!poz[val]){
                    h[++l] = val;
                    poz[h[l]] = l;
                    urc(l);
                }
            }
            nou = nou->urm;
        }
    }
}
bool negativ(int n){
    int y,z;
    for(int i=1;i<=n;i++){
        nod *nou = v[i];
        while(nou){
            y = nou->nr;
            z = nou->cost;
            if(d[i] + z < d[y])
                return true;
            nou = nou->urm;
        }
    }
    return false;
}
int main()
{
    int n,m,z,y,x,ns = 1;
    in>>n>>m;
    for(int i=1;i<=m;i++){
        in>>x>>y>>z;
        adaug(x,y,z);
    }
    in.close();
    bell(ns,n);
    if(negativ(n))
        out<<"Ciclu negativ!\n";
    else
        for(int i=1;i<=n;i++)
            if(i != ns)
                out<<d[i]<<" ";
    out.close();
    return 0;
}