#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define INF 1000000005

vector <vector <pair <int, int> > > G;
vector <int> d, prcs, is;
queue <int> Q;

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

    int N, M;
    scanf("%d %d\n", &N, &M);

    G.resize(N + 1);
    prcs.resize(N + 1);
    d.resize(N + 1);
    is.resize(N + 1);

    for(int i = 2; i <= N; ++i) {
        d[i] = INF;
    }

    int x, y, cost;
    for(int i = 1; i <= M; ++i) {
        scanf("%d %d %d\n", &x, &y, &cost);

        G[x].push_back(make_pair(y, cost));
    }

    Q.push(1);
    is[1] = 1;
    prcs[1] = 1;
    while(!Q.empty()) {
        int node = Q.front();
        Q.pop();
        is[node] = 0;
        for(unsigned int z = 0; z < G[node].size(); ++z) {
            int nxt = G[node][z].first;
            int cost = G[node][z].second;

            if(d[nxt] > d[node] + cost) {
                d[nxt] = d[node] + cost;
                if(!is[nxt]) {
                    is[nxt] = 1;
                    Q.push(nxt);
                    prcs[nxt]++;
                    if(prcs[nxt] == N) {
                        cout << "Ciclu negativ!\n";
                        return 0;
                    }
                }
            }
        }
    }

    for(int i = 2; i < N; ++i) {
        cout << d[i] << ' ';
    }

    cout << d[N] << '\n';

    return 0;
}