#include <iostream>
#include <fstream>
#include <queue>
#define inf 1000000
#define maxn 50005
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,x,y,c,cn,viz[maxn],nr[maxn];
struct nod{
    int val,cost;
    nod *urm;
}*v[inf],*p;
queue<int>q;
vector<int> dist(maxn,inf);
void add()
{
    //cout<<x<<" "<<y<<" "<<c<<endl;
    p=new nod;
    p->val=y;p->cost=c;p->urm=v[x];v[x]=p;
    //p=new nod;
    //p->val=x;p->cost=c;p->urm=v[y];v[y]=p;
}
int main() {
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>x>>y>>c;
        add();
    }
    /*for(int i=1;i<=n;i++){
        cout<<i<<": ";
        for(nod *p=v[i];p;p=p->urm)
            cout<<p->val<<" ";
        cout<<endl;
    }*/
    q.push(1);
    dist[1]=0;
    while(!q.empty()&&!cn){
        x=q.front();
        q.pop();
        viz[x]=0;
        for(nod *p=v[x];p;p=p->urm){
            if(dist[x]<inf)
                if(dist[p->val]>dist[x]+p->cost){
                    dist[p->val]=dist[x]+p->cost;
                    if(nr[x]>=n)cn=1;
                    else{
                        q.push(p->val);
                        nr[p->val]++;
                        viz[p->val]=1;
                    }
                }
        }
    }
    if(cn)fout<<"Ciclu negativ!";
    else for(int i=2;i<=n;i++)
        fout<<dist[i]<<" ";
    fout<<'\n';
    return 0;
}