#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<pair<int,int>> pq;

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});
    }

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

    while (!pq.empty()) {
        auto[from,cost] = pq.front();
        pq.pop();
        vis[from] = 0;
        for (auto [to,w] : adj[from]) {
            if (cost + w < dist[to]) {
                dist[to] = cost + w;
                p[to] = from;
                if (!vis[to]) {
                    pq.push({to,w});
                    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";
    }
}