#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50005;
const int INF = 1e9;

int n,m;

vector <pair<int,int>> adj[NMAX];

bool circuitNegativ=false;

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

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

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

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

            if (d[u]!=INF && cost+d[u]<d[v]){
                d[v]=cost+d[u];
                relax[v]++;
                if (inQueue[v]==false){
                    inQueue[v]=true;
                    q.push(v);
                }
            }

            if (relax[v]>=n){
                circuitNegativ=true;
                break;
            }
        }
    }

    return d;
}

int main(){
    f>>n>>m;
    for (int i=1;i<=m;i++){
        int nod1, nod2, cost;
        f>>nod1>>nod2>>cost;
        adj[nod1].push_back({nod2, cost});
    }

    vector <int> dist = BellmanFord(1);

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

}