#include <bits/stdc++.h>

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

const int inf=0x3f3f3f3f;
const int nmax=50002;

vector < pair<int, int> > G[nmax];
queue <int> Q;

int n,m,isq[nmax],nrq[nmax],v[nmax];
bool nc=0;

void bell(int node){
    memset(v,inf,sizeof v);
    Q.push(node);
    v[node]=0;
    isq[node]=1;
    nrq[node]=1;
    while(!Q.empty() && !nc){
        int q=Q.front();
        Q.pop();
        isq[q]=0;
        for(auto nn: G[q])
            if(v[q]+nn.second<v[nn.first]){
                v[nn.first]=v[q]+nn.second;
                if(!isq[nn.first]){
                    if(nrq[q]==n)nc=1;
                    else{
                        Q.push(nn.first);
                        isq[nn.first]=1;
                        nrq[nn.first]++;
                    }
                }
            }
    }
}

int main()
{
    int a,b,c;
    fin>>n>>m;
    for(int i=1;i<=m;++i){
        fin>>a>>b>>c;
        G[a].push_back({b,c});
    }
    bell(1);
    if(nc){
        fout<<"Ciclu negativ!\n";
        return 0;
    }
    for(int i=2;i<=n;++i)fout<<v[i]<<' ';
    return 0;
}