#include<fstream>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

#define FOR(a,b,c) for (int a=b;a<=c;++a)
#define Nmax 50100
#define inf 50100100

int N,M;
int d[Nmax],nr_in_coada[Nmax];
bool ciclunegativ=false;

struct elem {
    int y,dist;
};
vector<elem> v[Nmax];
queue<elem> Q;

bool operator <(elem a,elem b) {
    return a.dist>b.dist;
}

int main() {
    f>>N>>M;
    FOR (i,1,M) {
        int x,y,d;
        f>>x>>y>>d;
        elem A;
        A.y=y;
        A.dist=d;
        v[x].push_back(A);
    }
    FOR (i,2,N) {
        d[i]=inf;
    }
    elem A;
    A.y=1;
    A.dist=-1;
    Q.push(A);
    while (!Q.empty() && !ciclunegativ) {
        elem A=Q.front();
        Q.pop();
        int nod=A.y;
        if (d[nod]<A.dist) {
            continue;
        }
        ++nr_in_coada[nod];
        if (nr_in_coada[nod]>N) {
            ciclunegativ=true;
            break;
        }
        vector<elem>::iterator it;
        for (it=v[nod].begin();it<v[nod].end();++it) {
            int vecin=it->y;
            if (d[vecin]>d[nod]+it->dist) {
                d[vecin]=d[nod]+it->dist;
                elem B;
                B.y=vecin;
                B.dist=d[vecin];
                Q.push(B);
            }
        }
    }
    if (ciclunegativ) {
        g<<"Ciclu negativ!";
        return 0;
    }
    FOR (i,2,N) {
        if (d[i]==inf) {
            g<<"0 ";
        }
        else {
            g<<d[i]<<' ';
        }
    }
    f.close();g.close();
    return 0;
}