#include <bits/stdc++.h>
using namespace std;

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

const int dim=50009,inf=1e9;

struct elem{
    int y,c;
};

vector<elem>v[dim];
queue<int>q;

int n,m;
int d[dim],cnt[dim];
bool inqueue[dim],ciclu;

void BellmanFord(int start){

    d[start]=0;
    q.push(start);
    inqueue[start]=true;

    while(!q.empty()){
        int x=q.front();
        q.pop();
        inqueue[x]=false;

        for(auto nod:v[x]){
            int y=nod.y;
            int cost=nod.c;
            if(d[x]+cost<d[y]){
                d[y]=d[x]+cost;
                if(!inqueue[y]){
                    q.push(y);
                    inqueue[y]=true;
                    cnt[y]++;
                    if(cnt[y]>n){
                        ciclu=true;
                        return;
                    }
                }
            }
        }
    }
}

signed main(){
        fin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        fin>>x>>y>>c;
        v[x].push_back({y,c});
    }
    for(int i=1;i<=n;i++){
        d[i]=inf;
    }
    BellmanFord(1);
    if(ciclu){
        fout<<"Ciclu negativ!";
    }
    else{
        for(int i=2;i<=n;i++){
            fout<<d[i]<<' ';
        }
    }
}