#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

const int MAXN = 50005;
const long long INF = 1e18;

int n, m;

vector<pair<int, long long>> adj[MAXN];

bool cicluNegativ = false;

vector<long long> BellmanFord_QUEUE(int start){
    vector<long long> d(n+1, INF);
    vector<bool> inQueue(n+1, false);
    vector<int> countRelax(n+1, 0);
    queue<int> q;

    d[start]=0;
    q.push(start);
    inQueue[start]=true;

    while (!q.empty()) {
        int u=q.front();
        q.pop();
        inQueue[u]=false;

        for (const auto& edge : adj[u]) {
            int v=edge.first;
            long long cost=edge.second;

            if (d[u]!=INF && d[u]+cost<d[v]) {
                d[v]=d[u]+cost;
                countRelax[v]++;

                if (countRelax[v]>=n) {
                    cicluNegativ=true;
                    return d;
                }

                if (inQueue[v]==false) {
                    q.push(v);
                    inQueue[v]=true;
                }
            }
        }
    }
    return d;
}

int main() {
    f>>n>>m;

    for (int i=1;i<=m;i++) {
        int x, y;
        long long c;
        f>>x>>y>>c;

        adj[x].push_back({y, c});
    }

    vector<long long> dist = BellmanFord_QUEUE(1);

    if (cicluNegativ==true) {
        g<<"Ciclu negativ!"<<'\n';
    } else {
        for (int i=2;i<=n;i++) {
            if (dist[i]==INF) g<<0<<" ";
            else g<<dist[i]<<" ";
        }
    }

    return 0;
}