#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <vector>

using namespace std;

const int nmax=50000, inf=1<<30;

struct str{
    int x, y;
};

inline str mp(int x, int y){
    str aux;
    aux.x=x; aux.y=y;
    return aux;
}

bool u[nmax+1];
char *buffer;
int d[nmax+1], cnt[nmax+1];
queue <int> q;
vector <str> g[nmax+1];

void read_int(int &x){
    int ok;
    while ((*buffer<'0'|| *buffer>'9')&& *buffer!='-'){
        ++buffer;
    }

    if (*buffer=='-'){
        ok=-1;
        ++buffer;
    }else{
        ok=1;
    }
    x=0;
    while (*buffer>='0'&& *buffer<='9'){
        x=x*10+*buffer-'0';
        ++buffer;
    }
    x*=ok;
}

int main(){
    bool neg_cyc;
    int fs, n, m;

    assert(freopen("bellmanford.in", "r", stdin));
    fseek(stdin, 0, SEEK_END);
    fs=ftell(stdin);
    buffer=(char*)malloc(fs);
    rewind(stdin);
    assert(fread(buffer, 1, fs, stdin));
    fclose(stdin);
    
    read_int(n); read_int(m);
    for (; m; --m){
        int x, y, z;

        read_int(x); read_int(y); read_int(z);
        g[x].push_back(mp(y, z));
    }
    fclose(stdin);

    for (int i=2; i<=n; ++i){
        d[i]=inf;
    }

    neg_cyc=0;
    q.push(1);
    u[1]=1;
    cnt[1]=1;
    while (!q.empty()&& !neg_cyc){
        int x;

        x=q.front();
        q.pop();
        u[x]=0;
        for (vector <str>::iterator it=g[x].begin(); it!=g[x].end(); ++it){
            if (d[it->x]>d[x]+(it->y)){
                d[it->x]=d[x]+(it->y);
                if (!u[it->x]){
                    if (cnt[it->x]>n){
                        neg_cyc=1;
                        break;
                    }else{
                        q.push(it->x);
                        u[it->x]=1;
                        ++cnt[it->x];
                    }
                }
            }   
            
            /*fprintf(stderr, "\n%d->%d:", x, it->x);
            for (int i=1; i<=n; ++i){
                fprintf(stderr, " %d", d[i]);
            }*/
        }
    }

    assert(freopen("bellmanford.out", "w", stdout));
    if (neg_cyc){
        printf("Ciclu negativ!\n");
    }else{
        for (int i=2; i<=n; ++i){
            printf("%d ", d[i]);
        }
        printf("\n");
    }
    fclose(stdout);

    return 0;
}