#include<bits/stdc++.h>
#define INFILE "bellmanford.in"
#define OUTFILE "bellmanford.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
const int INF=INT_MAX;
struct Graph{
    vector<vector<pair<int,int>>> Adj;
    void Init(int n){
        Adj.resize(n+1);
    }
    void Add(int x,int y,int c){
        Adj[x].push_back({y,c});
    }
}G;
int N,M;
void Read(){
    in>>N>>M;
    G.Init(N);
    for(int i=1;i<=M;i++){
        int x,y,c;
        in>>x>>y>>c;
        G.Add(x,y,c);
    }
}

void BellmanFord(){
    vector<int> dist(N+1,INF);
    vector<int> counter(N+1,0);
    vector<bool> inQueue(N+1,false);
    bool negativeCycle=false;
    queue<int> coada;
    coada.push(1);
    dist[1]=0;
    inQueue[1]=true;
    while(!coada.empty()&&!negativeCycle){
        int x=coada.front();
        coada.pop();
        inQueue[x]=false;
        if(dist[x]==INF) continue;
        for(auto edge:G.Adj[x]){
            int y=edge.first;
            int c=edge.second;
            if(dist[y]>dist[x]+c){
                dist[y]=dist[x]+c;
                if(!inQueue[y]){
                    if(counter[y]>N){
                        negativeCycle=true;
                    }
                    else{
                        coada.push(y);
                        inQueue[y]=true;
                        counter[y]++;
                    }
                }
            }
        }
    }
    if(negativeCycle){
        out<<"Ciclu negativ!\n";
    }
    else{
        for(int i=2;i<=N;i++){
            out<<dist[i]<<" ";
        }
    }
}

int main(){
    Read();
    BellmanFord();
}