#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <fstream>
#include <queue>

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

std::vector<pair<int,int>> muchii[50006];

int main() {
    int n,m;
    f>>n>>m;
    for (int i=0;i<m;i++) {
        int x,y,cost;
        f>>x>>y>>cost;
        muchii[x-1].emplace_back(y-1,cost);
    }
    int updates[50006]={0};
    int distance[50006];
    bool visited[50006];
    for (int i=0;i<n;i++) {
        visited[i]=false;
        distance[i]=100000000;
    }
    distance[0]=0;
    visited[0]=true;
    queue<int> toCheck;
    toCheck.push(0);
    while (!toCheck.empty()){
        int x=toCheck.front();
        visited[x]=false;
        toCheck.pop();
        for (auto [y,cost]:muchii[x]) {
            if (distance[x]+cost<distance[y]) {
                if (visited[y]==false) {
                    toCheck.push(y);
                    visited[y]=true;
                    updates[y]+=1;
                }
                if (updates[y]==n) {
                    g<<"Ciclu negativ!";
                    return 0;
                }
                distance[y]=distance[x]+cost;
            }
        }
    }

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

}