#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);



    d[start]=0;

    queue<int> actprev;
    actprev.push(start);
    int ok=true;
    for (int i=1;i<=n-1;i++){
            queue<int> act;
            while(actprev.size()>0){
                int u=actprev.front();
                actprev.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];

                         act.push(v);

                        }
                    }
              actprev=act;
                }
    }

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

                    if (d[u]!=INF && cost+d[u]<d[v]){
                            circuitNegativ=true;
                        return d;
                    }
                }
    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]<<" ";
        }
    }

}