#include <fstream>
#define INF 100000000
#define NMAX 5000
using namespace std;
 
//FILE * intrare = fopen("bellmanford.in","r");
//FILE * iesire = fopen("bellmanford.out","w");
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
 
struct nod{
    int ind, val;
};
 
nod M[NMAX][NMAX];
int n, m;
int cmin[NMAX];
int sch;
int nr[NMAX];
int nrpus[NMAX];
int coada[NMAX];
 
void citire();
void bmf();
void afisare();
 
int main(){
    citire();
    bmf();
    afisare();
    return 0;
}
 
void citire(){
    int i,x,y,cst;
    nod nd;
    //fscanf(intrare,"%d%d",&n,&m);
    fin>>n>>m;
    for(i = 1; i <= m; i++){
        //fscanf(intrare,"%d%d%d",&x,&y,&cst);
        fin>>x>>y>>cst;
        nd.ind = y;
        nd.val = cst;
        M[x][++nr[x]] = nd;
    }
    for(i = 1; i <= n; i++)
        cmin[i] = INF;
    cmin[1] = 0;
}
 
void bmf(){
    int inc, sf;
    int i, x;
    inc = sf = 1;
    coada[1] = 1;
    sch = 0;
    while(inc <= sf){
        x=coada[inc++];
        for(i = 0;i<=nr[x];i++)
            if(cmin[x]+M[x][i].val<cmin[M[x][i].ind]){
                cmin[M[x][i].ind]=cmin[x]+M[x][i].val;
                coada[++sf]=M[x][i].ind;
                nrpus[M[x][i].ind]++;
                if(nrpus[M[x][i].ind] >= n){
                    sch = 1;
                    return;
                }
            }
    }
}
 
void afisare(){
    int i;
    if(sch)
        //fprintf(iesire,"Ciclu negativ!");
        fout<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
            //fprintf(iesire,"%d ",cmin[i]);
            fout<<cmin[i]<<' ';
    //fprintf(iesire,"\n");
    fout<<'\n';
    //fclose(iesire);
    fout.close();
}