#include <cstdio>
#include <queue>
#include <vector>
#define n_max 50002
#define inf 0x3f3f3f3f

using namespace std;

vector < pair <int,int> > G[n_max];
queue <int> Q;
int viz[n_max],nr[n_max],d[n_max];
int n,m;

void read() {
    int i,j,k,c;
    scanf("%d %d",&n,&m);
    for (k=1; k<=m; k++) {
        scanf("%d %d %d",&i,&j,&c);
        G[i].push_back(make_pair(j,c));
    }
}

bool bellman_ford() {
    int prec,i;
    for (i=1; i<=n; i++)
        d[i]=inf;
    d[1]=0;
    Q.push(1);
    while (!Q.empty()) {
        prec=Q.front();
        Q.pop();
        viz[prec]=0;
        for (vector < pair <int,int> >::iterator it=G[prec].begin(); it!=G[prec].end(); it++)
            if (d[prec]+it->second<d[it->first]){
                d[it->first]=d[prec]+it->second;
                if (viz[it->first]==0) {
                    viz[it->first]=1;
                    Q.push(it->first);
                    nr[it->first]++;
                }
                if (nr[it->first]>n-1)
                    return false;
            }
    }
    return true;
}

int main () {
    freopen ("bellmanford.in", "r", stdin);
    freopen ("bellmanford.out","w",stdout);
    read();
    if (bellman_ford())
        for (int i=2; i<=n; i++)
            printf("%d ",d[i]);
    else
        printf("%s","Ciclu negativ!");
    fclose(stdin);
    fclose(stdout);
    return 0;
}