#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define oo 0x3f3f3f3f

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n, m;
vector<bool> visited;
vector<int> dist, visitCount;
vector<vector<pair<int, int>>> graph;

void read() {
    f>>n>>m;
    
    visited.resize(n + 1, false);
    dist.resize(n + 1, oo);
    visitCount.resize(n + 1, 0);
    graph.resize(n + 1, vector<pair<int, int>>());

    int nodeX, nodeY, cost;
    for(int i = 0;i < m;++i) {
        f>>nodeX>>nodeY>>cost;
        graph[nodeX].push_back(make_pair(nodeY, cost));
    }
}

void solve() {
    dist[1] = 0;
    queue<int> bellman;
    bellman.push(1);

    while(!bellman.empty()) {
        int node = bellman.front();

        for(const auto& [neighbour, cost] : graph[node]) {
            if(dist[neighbour] < dist[node] + cost) {
                continue;
            }

            dist[neighbour] = dist[node] + cost;
            if(!visited[neighbour]) {
                bellman.push(neighbour);
            }
            visitCount[neighbour]++;

            if(visitCount[neighbour] >= n) {
                g<<"Ciclu negativ!";
                return;
            }
        }

        bellman.pop();
        visited[node] = false;
    }

    for(int i = 2;i <= n;++i) {
        g<<dist[i]<<" ";
    }
}

int main() {
    read();
    solve();

    return 0;
}