#include <fstream>
#define inf 1<<30

using namespace std;

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

struct graf{
    int nod,cost;
    graf *urm;
}*v[50005];

int use[50005],f[50005],c[50005];
int Q[50005],n,m,OK;

void add(int a, int b, int c){
    graf *p=new graf;
    p->nod=b;
    p->cost=c;
    p->urm=v[a];
    v[a]=p;
}
void bell(){
    int p,u,x;
    graf *nod;
    p=u=1;
    Q[1]=1; f[1]++;
    for(;p<=u;){
        x=Q[p];use[x]=0; p++;
        for(nod=v[x];nod;nod=nod->urm){
            if(c[nod->nod]>nod->cost+c[x]){
                    c[nod->nod]=nod->cost+c[x];
                if(!use[nod->nod]){
                    use[nod->nod]=1;
                    Q[++u]=nod->nod;
                    f[nod->nod]++;
                }
                if(f[nod->nod]>n){
                    OK=1;
                    return;
                }
            }
        }
    }
}
int main()
{
    int a,b,d;
    fin>>n>>m;
    for(int i=1;i<=m;i++){
        fin>>a>>b>>d;
        add(a,b,d);
    }
    for(int i=2;i<=n;i++)
        c[i]=inf;
    bell();
    if(!OK)
        for(int i=2;i<=n;i++)
            fout<<c[i]<<' ';
    else
        fout<<"Ciclu negativ!";
    return 0;
}