#include<bits/stdc++.h>

using namespace std;

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

vector<vector<pair<int,int>>> adj(250005);
vector<int> vis(50005, 0);
vector<int> dist(50005, INT_MAX);
vector<int> p(50005, -1);
queue<int> q;

int n, m;

int bellman_ford() {

    fin >> n >> m;

    for (int i = 0 ; i < m ; i++) {
        int x,y,c;
        fin >> x >> y >> c;
        adj[x].push_back({y,c});
    }

    q.push(1);
    dist[1] = 0;
    vis[1] = 1;
    vector<int> negativ (50005, 0);

    while (!q.empty()) {
        auto from = q.front();
        q.pop();
        vis[from] = 0;
        for (auto [to,w] : adj[from]) {
            if (dist[from] + w < dist[to]) {
                dist[to] = dist[from] + w;
                p[to] = from;
                if (!vis[to]) {
                    q.push(to);
                    vis[to] = 1;
                }
                negativ[to] = negativ[from] + 1;
                if (negativ[to] > n) {
                    return false;
                }
            }
        }
    }
    return true;
}

int main() {
    if (bellman_ford()) {
        for (int i = 2; i <= n; i++) {
            if (dist[i] == INT_MAX) {
                fout << 0 << " ";
            }else {
                fout << dist[i] << " ";
            }
        }
    }else {
        fout << "Ciclu negativ!";
    }
}