#include <cstdio>
#include <cstring>
#include <cstdlib>
// ATENTIE LA CITIRE!
#include <vector>
#include <queue>
#define f "bellmanford.in"
#define g "bellmanford.out"
#define nmax 50001
#define inf 0x3f3f3f
#define verf ++poz == hg ? fread ( ch, 1, hg, stdin ), poz = 0 : 0
#define hg 1 << 13
using namespace std;

vector < pair<int, int> > gf[nmax];
int d[nmax], viz[nmax], c_neg[nmax], n, m, poz;
char ch[hg];

inline void cit ( int &x ) {
    int semn = 1;
    if ( ch[0] == '\0' ) fread ( ch, 1, hg, stdin ) ;
    else for ( ; (ch[poz] < '0' || ch[poz] > '9') && ch[poz] != '-' ; verf ) ;
    for ( x = 0 ; ch[poz] >= '0' && ch[poz] <= '9' || ch[poz] == '-' ; (ch[poz] == '-' ? semn = -1 : x = x * 10 + ch[poz] - '0'), verf ) ;
    x *= semn;
}

struct comp{
    bool operator () (const int &a, const int &b){
        return d[a]>d[b];
    }
};

bool bellman_ford(){
    memset(d, inf, sizeof(d));//initializez vectorul distantelor minime cu valoarea inf
    viz[1]=1;//marchez nodul de plecare ca vizitat
    d[1]=0;//initializez punctul de plcare cu 0;
    priority_queue<int, vector<int>, comp > Q;//declar coada prioritara
    for(Q.push(1); !Q.empty();){//bag in coada nodul de plecare/si cat timp aceasta nu e goala
        int nod_princ = Q.top();//initializez nod_princul principal cu topul cozii;
        viz[nod_princ]=0;//demarchez nodul principal
        Q.pop();
        for(vector< pair<int, int> >::iterator it=gf[nod_princ].begin(); it!=gf[nod_princ].end(); it++){//pt fiecare vecin al nodului principal
            int vecin = it->first;//vecin;
            int cost = it->second;//costul distantei : nod principal - vecin
            if (d[vecin] > d[nod_princ] + cost){//daca pot minimaliza distanta vecinului prin nodul principal atunci
                d[vecin] = d[nod_princ] + cost;//distanta vecinului ia valoara sumei dintre distanta nod_princ si costul de la nod princ la vecin
                if(viz[vecin] == 0){// daca nu am mai vizitat acest vecin(nod) atunci
                    if(c_neg[vecin] > n)//daca am folosit vecin de mai mult de n ori atunci am CICLU NEGATIV
                        return 1;// si returnez valoarea true(1);
                    else {
                        Q.push(vecin);// bag vecinul in coada
                        c_neg[vecin]++;//cresc c_neg[vecin]++;
                        viz[vecin]=1;//marchez vecinul ca si vizitat;
                    }
                }
            }
        }
    }
    return 0;
}


int main(){
    freopen(f, "r", stdin);
    freopen(g, "w", stdout);
    //scanf("%d %d\n", &n, &m);
    cit(n);cit(m);

    for(int i=1; i<=m; i++){
        int x, y, c;
        //scanf("%d %d %d\n", &x, &y, &c);
        cit(x); cit(y); cit(c);
        gf[x].push_back(make_pair(y,c));
    }
    if (bellman_ford()==0)
        for(int i=2; i<=n; i++)
            if (d[i] >= inf) printf("0");
            else printf("%d ",d[i]);
    else printf("Ciclu negativ!");

    return 0;
}