#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 distance[50006];
    for (int i=0;i<n;i++) {
        distance[i]=100000000;
    }
    distance[0]=0;
    queue<int> toCheck;
    set<int> nextToCheck;
    toCheck.push(0);
    for (int i=0;i<n;i++) {

        while (!toCheck.empty()){
            int x=toCheck.front();
            toCheck.pop();
            for (auto [y,cost]:muchii[x]) {
                if (distance[x]+cost<distance[y]) {
                    nextToCheck.insert(y);
                    distance[y]=distance[x]+cost;
                }
            }
        }
        for (auto x:nextToCheck)
            toCheck.push(x);
        if (toCheck.empty()) {
            break;
        }
    }
    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]<<" ";
    }

}