#include <bits/stdc++.h>

using namespace std;

int M, N, S;
vector<vector<pair<int, int>>> G;
vector<int> D;
vector<int> C;

/*void bfs(int node) {
    queue<int> Q;
    Q.push(node);
    D[node] = 0;
    while(!Q.empty()) {
        node = Q.front();
        Q.pop();
        if(V[node])
            continue;
        V[node] = true;
        for(auto neigh : G[node]) {
            if(D[neigh] == -1) {
                D[neigh] = D[node] + 1;
                Q.push(neigh);
            }
        }
    }
}*/

bool bellman(int node)
{
    queue<int> Q;
    Q.push(node);
    D[node] = 0;
    while(!Q.empty())
    {
        node = Q.front();
        Q.pop();
        if(C[node] > N)
            return false;

        for(pair<int, int> neigh : G[node])
        {
            int cost = neigh.second;
            if(D[neigh.first] > cost + D[node])
            {
                D[neigh.first] = cost + D[node];
                Q.push(neigh.first);
                C[neigh.first]++;
            }
        }
    }

    return true;
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    cin >> N >> M;

    G.resize(N + 1);
    D.resize(N + 1);
    C.resize(N + 1);
    fill(D.begin(), D.end(), INT_MAX);
    fill(C.begin(), C.end(), 0);

    for(int i = 1; i <= M; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        G[x].push_back({y, c});
    }

    if(bellman(1))
    {
        for(int i = 2; i <= N; i++)
        {
            cout << D[i] << " ";
        }
    }
    else
    {
        printf("Ciclu negativ!\n");
    }

    return 0;
}