#include <bits/stdc++.h>

using namespace std;

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

#define Nmax 300000
#define INF 999999999

vector <pair <int, int> > G[Nmax];
deque <int> Q;

bool neg=1;
int n,m,L[Nmax],x,y,c;

void bellman_ford(){

    int node;


    while(!Q.empty()){
        node=Q.front();
        Q.pop_front();
        for(int i=0;i<G[node].size();i++){
            if(L[G[node][i].first] > L[node] + G[node][i].second){
                L[G[node][i].first] = L[node] + G[node][i].second;
                Q.push_back(G[node][i].first);

            }
        }
    }

}

int check_neg(){
    int s=0;
    for(int i=1;i<=n;i++){
        s+=L[i];
    }
    if(s<0)
        return 0;
    return 1;
}
int main()
{
    in>>n>>m;
    for(int i=2;i<=n;i++)
        L[i]=INF;
    for(int i=1;i<=m;i++){
        in>>x>>y>>c;
        G[x].push_back({y,c});
    }
    Q.push_back(1);
    bellman_ford();
    if(check_neg() == 0)
        out<<"Ciclu Negativ";
    else
        for(int i=2;i<=n;i++)
            out<<L[i]<<" ";
    return 0;
}