#include <bits/stdc++.h>

using namespace std;

vector < pair < int , int>> graff [50001];
int dist[50001];
int freq[50001];
queue < pair <int, int >> qq;

int main() {
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int n , m;
    f >> n >> m;
    for (int i = 1; i <= m ;i ++){
        int from , to , cost;
        f >> from >> to >> cost;
        graff[from].push_back({to , cost});
    }

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

    qq.push({1, 0});
    freq[1] = 1;
    while(!qq.empty()){
        int frontValues = qq.front().first;
        int frontValueCost = qq.front().second;
        qq.pop();

        for (auto next : graff[frontValues]){
            int nextValue = next.first;
            int nextCost = next.second;

            if (dist[frontValues] + nextCost < dist[nextValue] ){
                dist[nextValue] = dist[frontValues] + nextCost;
                freq[nextValue] ++;
                qq.push({nextValue, dist[nextCost]});
            }

            if (freq[nextValue] >= n){
                g << "Ciclu negativ!";
                return 0;
            }
        }
    }
    for (int i = 2; i <= n; i++){
        g << dist[i] << " ";
    }
    return 0;
}