#include <cassert>
#include <cstdio>
#include <cstdlib>
#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;
}

char *buffer;
int d[nmax+1];
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(){
    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;
    }

    for (int i=1; i<n; ++i){
        for (int j=1; j<=n; ++j){
            if (d[j]<inf){
                for (vector <str>::iterator it=g[j].begin(); 
                    it!=g[j].end(); ++it){
                
                    if (d[j]+(it->y)<d[it->x]){
                        d[it->x]=d[j]+(it->y);
                    }
                }
            }
        }
    }

    for (int i=1; i<=n; ++i){
        for (vector <str>::iterator it=g[i].begin(); it!=g[i].end(); ++it){
            if (d[i]+(it->y)<d[it->x]){
                assert(freopen("bellmanford.out", "w", stdout));
                printf("Ciclu negativ!");
                fclose(stdout);
                
                return 0;
            }
        }
    }

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

    return 0;
}