#include <cstdio>
using namespace std;
#define NMAX 50000
#define MMAX 250000
#define INFINIT 1000000000

bool nochange = false;
int n, m, d[NMAX], a[MMAX], b[MMAX], c[MMAX];
int i, j;
FILE *fin, *fout;

int main(){

    fin = fopen("bellmanford.in", "r");
    fout = fopen("bellmanford.out", "w");

    fscanf(fin, "%d %d", &n, &m);
    for(i=1; i<=n; i++)
        d[i] = INFINIT;
    d[1] = 0;
    for(i=1; i<=m; i++){
        fscanf(fin, "%d %d %d", &a[i], &b[i], &c[i]);
    }

    for(i=1; i<=n-1; i++){
        nochange = true;
        for(j=1; j<=m; j++){
            if(d[ b[j] ] > d[ a[j] ] + c[j]){
                d[ b[j] ] = d[ a[j] ] + c[j];
                nochange = false;
            }
        }
        if(nochange)
            break;
    }

    for(j=1; j<=m; j++){
            if(d[ b[j] ] > d[ a[j] ] + c[j]){
                fprintf(fout, "Ciclu negativ!");
                break;
            }
        }

    for(i=2; i<=n; i++)
        fprintf(fout, "%d ", d[i]);

    return 0;
}