#include <fstream>
#include <vector>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
const int N = 50005, M = 1000000005;
int d[N], h[N];
bool inHeap[N];
vector < pair< int,int > > v[N];
void upHeap(int f){
    while(f/2 && d[h[f]] < d[h[f/2]]){
        swap(h[f],h[f/2]);
        f /= 2;
    }
}
void insertHeap(int val, int &l){
    h[++l] = val;
    inHeap[val] = true;
    upHeap(l);
}
void downHeap(int l){
    int f = 0, t = 1;
    while(t != f){
        f = t;
        if(f*2 <= l && d[h[t]] > d[h[f*2]])
            t = f*2;
        if(f*2 + 1 <= l && d[h[t]] > d[h[f*2+1]])
            t = f*2+1;
        swap(h[t],h[f]);
    }
}
int extractTop(int &l){
    int rad = h[1];
    inHeap[rad] = false;
    swap(h[1], h[l--]);
    inHeap[h[1]] = true;
    downHeap(l);
    return rad;
}
void bell(int ns, int n, int m){
    int l = 0, rad, c, val, pas = 0, sz;
    for(int i=1;i<=n;i++)
        d[i] = M;
    d[ns] = 0;
    insertHeap(ns,l);
    while(l && pas <= 1LL*n*m){
        pas++;
        rad = extractTop(l);
        sz = v[rad].size();
        for(int i=0;i<sz;i++){
            val = v[rad][i].first;
            c = v[rad][i].second;
            if(d[val] > d[rad] + c){
                d[val] = d[rad] + c;
                if(inHeap[val] == false)
                    insertHeap(val,l);
            }
        }
    }
}
bool negativ(int n){
    int y, z, sz;
    for(int i=1;i<=n;i++){
        sz = v[i].size();
        for(int j=0;j<sz;j++){
            y = v[i][j].first;
            z = v[i][j].second;
            if(d[y] > d[i] + z)
                return true;
        }
    }
    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;
        v[x].push_back({y,z});
    }
    in.close();
    bell(ns,n,m);
    if(negativ(n))
        out<<"Ciclu negativ!\n";
    else
        for(int i=1;i<=n;i++)
            if(i != ns)
                out<<d[i]<<" ";
    out<<"\n";
    out.close();
    return 0;
}