#include <fstream>
#include <vector>

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

struct Edge {
    int a, b , cost;
};
vector<Edge> muchii;
int n, m;
int dist[250001];
const int INF = 1e9;
int main() {
    in>>n>>m;
    for(int i=0; i<m; i++) {
        int u, v, w;
        in>>u>>v>>w;
        muchii.push_back({u,v,w});
    }
    for(int i=1; i<=n; i++) {
        dist[i] = INF;
    }
    dist[1] = 0;
    for(int i=0; i<n-1; i++) {
        bool flag = false;
        for (auto& m: muchii) {
            if (dist[m.a]!=INF&& dist[m.b]>dist[m.a]+m.cost) {
                dist[m.b] = dist[m.a] + m.cost;
                flag = true;
            }
        }
        if (!flag) {
            break;
        }

    }
    bool negativ_cycle = false;
    for (auto& m: muchii) {
        if (dist[m.a]!=INF&& dist[m.b]>dist[m.a]+m.cost) {
            negativ_cycle = true;
            break;
        }
    }
    if (negativ_cycle) {
        out<< "Ciclu negativ!";
    }
    else {
        for (int i=2; i<=n; i++) out<<dist[i]<<" ";
    }
    return 0;
}