#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int inf=1<<25;

int D[50005];
int ITER[50005];
int INQ[50005];
vector<pair<int,int>> L[50005];
int n,m,p;

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

void read(){
    int x,y,d;
    in>>n>>m;
    p=1;
    for(int i=1;i<=m;i++){
        in>>x>>y>>d;
        L[x].push_back({y,d});
    }
}
bool bellman(int st){
    int nod;
    queue<int> Q;
    D[st]=0;
    Q.push(st);
    while(!Q.empty()){
        nod=Q.front();
        Q.pop();
        INQ[nod]=0;
        for(auto x : L[nod]){
            if(D[x.first]>D[nod]+x.second){
                D[x.first]=D[nod]+x.second;
                ITER[x.first]++;
                if(ITER[x.first]>n)
                    return 0;
                if(!INQ[x.first]){
                    Q.push(x.first);
                    INQ[x.first]=1;
                }
            }
        }
    }
    return 1;
}
void solve(){
    for(int i=1;i<=n;i++)
        D[i]=inf;
    if(bellman(1))
        for(int i=2;i<=n;i++)
            out<<D[i]<<" ";
    else out<<"Ciclu negativ!";
}
int main(){
    read();
    solve();
    return 0;
}