#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);
vector <int> viz(n+1, 0);


    d[start]=0;

    int ok=true;
    for (int i=1;i<=n-1;i++){
        if (ok==false) return d;
        ok=false;
        for(int u=1;u<=n;u++)
            if (viz[u]==i-1)
                for (auto edge : adj[u]){
                    int v=edge.first;
                    int cost=edge.second;

                    if ( cost+d[u]<d[v]){
                        d[v]=cost+d[u];
                        viz[v]=i;
                            /// tata[m.v]=m.u;
                         ok=true;
                        }
                    }
                }

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

                    if ( 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]<<" ";
        }
    }

}