#include<fstream>
#include<bitset>
#include<algorithm>
#include<vector>
#include<queue>

using namespace std;

#define Nmax 50001

vector<pair<int, int> > G[Nmax];
queue<int> Q;
bitset<Nmax> viz;

int N, M, Sursa, D[Nmax], frecv[Nmax];
bool ok;

void bellmanford(int Sursa) {

    int nod, fiu, cost;
    vector<pair<int, int> >:: iterator it, it2;

    fill(D+1, D+N+1, 1<<30);

    frecv[Sursa] = 1;
    viz[Sursa] = 1;
    D[Sursa] = 0;
    Q.push(Sursa);

    while(!Q.empty()) {
        nod = Q.front();
        viz[nod] = 0;
        Q.pop();
        it2 = G[nod].end();
        for(it = G[nod].begin(); it!=it2; ++it) {
            fiu = it->first;
            cost = it->second;
            if(D[fiu] > D[nod] + cost) {
                D[fiu] = D[nod] + cost;
                if(!viz[fiu]) {
                    viz[fiu] = 1;
                    frecv[fiu]++;
                    if(frecv[fiu] >= N-1) {
                        ok = 0;
                        return;
                    }
                    Q.push(fiu);
                }
            }
        }
    }

    ok = 1;

}


int main() {

    int i, x, y, c;

    ifstream f("bellmanford.in");
    f>>N>>M;
    while(M--) {
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    f.close();

    Sursa = 1;
    bellmanford(Sursa);

    ofstream g("bellmanford.out");
    if(ok)
        for(i=2; i<=N; ++i)
            g<<D[i]<<" ";
    else
        g<<"Ciclu negativ!";
    g.close();

    return 0;
}