#include <iostream>
#include <vector>
#include <fstream>
#include <climits>
#include <queue>

#define Nmax 50010

using namespace std;

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

struct Edge {
    int dest, weight;
};

int n, m;
vector<Edge> graph[Nmax];
int visited[Nmax];

void solve(int startNode) {
    queue<int> q;
    vector<int> distances(n + 1, INT_MAX);

    q.push(startNode);
    distances[startNode] = 0;

    while(!q.empty()) {
        int current = q.front();
        q.pop();

        for(auto edge : graph[current]) {
            if(distances[edge.dest] > distances[current] + edge.weight) {
                distances[edge.dest] = distances[current] + edge.weight;
                q.push(edge.dest);
                visited[edge.dest]++;
                if(visited[edge.dest] >= n) {
                    fout << "Ciclu negativ!";
                    return;
                }
            }
        }
    }

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

int main() {
//    reading
    fin >> n >> m;
    for(int i = 0; i < m; i++) {
        int src, dest, weight;
        fin >> src >> dest >> weight;
        graph[src].push_back({dest, weight});
    }

    solve(1);
}