#include <bits/stdc++.h>

#define in  "bellmanford.in"
#define out "bellmanford.out"

using namespace std;

typedef pair<int, int> Edge;

const int NMAX = 250005;
const int INF = (1 << 30);

int N, M;
queue<int> Q;
vector<Edge> G[NMAX];
int dist[NMAX], marked[NMAX], inQueue[NMAX];

void InitSource() {
    for(int i = 1; i <= N; ++i) {
        marked[i] = 0;
        inQueue[i] = 0;
        dist[i] = INF;
    }
}

bool BellmanFord(int source) {
    InitSource();
    dist[source] = 0;
    Q.push(source);
    inQueue[source] = 1;

    while(!Q.empty()) {
        int curr = Q.front();
        marked[curr]++;
        if(marked[curr] >= N)
            return false;

        Q.pop();
        inQueue[curr] = 0;
        for(size_t i = 0; i < G[curr].size(); ++i) {
            int next = G[curr][i].first;
            int cost = G[curr][i].second;

            if(dist[next] > dist[curr] + cost) {
                dist[next] = dist[curr] + cost;

                if(!inQueue[next])
                    Q.push(next);
            }
        }
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL), cout.tie(NULL);

    freopen(in, "r", stdin);
    freopen(out, "w", stdout);

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

    if(BellmanFord(1))
        for(int i = 2; i <= N; ++i)
                cout << dist[i] << " ";
    else
        cout << "Ciclu Negativ!";


    return 0;
}