#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");

const int N_MAX = 5e4 + 5, oo = 2e9;
int N, M, NrQ[N_MAX], D[N_MAX];
vector < pair <int, int> > G[N_MAX];
queue <int> q;
bool InQ[N_MAX], ok = 1;

void BellmanFord(){
    for (int i = 2; i <= N; ++i)
        D[i] = oo;
    q.push(1);
    InQ[1] = 1;
    NrQ[1] = 1;
    while (!q.empty() && ok){
        int x = q.front(); q.pop(); InQ[x] = 0;
        for (auto vecin : G[x]){
            int node = vecin.first; int cost = vecin.second;
            if (!InQ[node]){
                q.push(node);
                InQ[node] = 1;
                D[node] = min(D[node], D[x] + cost);
                NrQ[node]++;
                if (NrQ[node] > N)
                    ok = 0;
            }
        }
    }
}

int main(){
    in >> N >> M;
    for (int i = 1; i <= M; ++i){
        int x, y, z; in >> x >> y >> z;
        G[x].push_back(make_pair(y, z));
    }
    BellmanFord();
    if (!ok)
        for (int i = 2; i <= N; ++i)
            out << D[i] * (D[i] != oo) << " ";
    else out << "Ciclu negativ!";
    out << '\n';
    return 0;
}