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

int d[nmax+1];
vector <str> g[nmax+1];

int main(){
    int n, m;

    assert(freopen("bellmanford.in", "r", stdin));
    assert(scanf(" %d %d ", &n, &m));
    for (; m; --m){
        int x, y, z;

        assert(scanf(" %d %d %d ", &x, &y, &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){
            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);
                }

                /*fprintf(stderr, "\n%d-%d:", j, it->x);
                for (int k=1; k<=n; ++k){
                    fprintf(stderr, " %d", d[k]);
                }*/            
            }
        }
    }

    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;
}