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

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 distance[50006];
    int predecessor[50006];
    for (int i=0;i<n;i++) {
        distance[i]=100000000;
        predecessor[i]=-1;
    }
    distance[0]=0;
    for (int i=0;i<n;i++) {
        for (int x=0;x<n;x++) {
            for (auto [y,cost]:muchii[x]) {
                if (distance[x]+cost<distance[y]) {
                    distance[y]=distance[x]+cost;
                    predecessor[y]=x;
                }
            }
        }
    }
    for (int i=0;i<n;i++) {
        for (int x=0;x<n;x++) {
            for (auto [y,cost]:muchii[x]) {
                if (distance[x]+cost<distance[y]) {
                    g<<"Ciclu negativ!";
                    return 0;
                }
            }
        }
    }
    for (int i=1;i<n;i++) {
        g<<distance[i]<<" ";
    }

}