#include<iostream>
#include<fstream>
#include<queue>
#define M  250010
#define N 50010
#define inf  1000000000
using namespace std;

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

struct muchie{int a,b,c;}e[M];
int n,m;
long d[N]; bool viz[N];
vector <int> v[N];

priority_queue <pair<int,int> > q;

void init(){
    int i;
    d[1]=0;
    for(i=2;i<=n;i++)
        d[i]=inf;
    q.push(make_pair(0,1));
    viz[1]=1;
}
void solve(){
    init();
    int nod,poz,dis,j,nv;
    while(q.size()){
        dis=q.top().first;
        nod=q.top().second;
        q.pop();
        for(j=0;j<v[nod].size();j++){
            nv=v[nod][j];
            if(d[e[nv].a]+e[nv].c<d[e[nv].b]){
                d[e[nv].b]=d[e[nv].a]+e[nv].c;
                if(!viz[e[nv].b]){
                    viz[e[nv].b]=1;
                    q.push(make_pair(-d[e[nv].b],e[nv].b));
                }
            }
        }
    }
}
bool ciclu_negativ(){
    int i;
    for(i=1;i<=m;i++)
        if(d[e[i].a]+e[i].c<d[e[i].b])
                return 1;
    return 0;
}
int main(){
    f>>n>>m; int i;
    for(i=1;i<=m;i++){
        f>>e[i].a>>e[i].b>>e[i].c;
        v[e[i].a].push_back(i);
    }
    solve();
    if(ciclu_negativ()) o<<"Ciclu negativ!";
    else{
        for(i=2;i<=n;i++)
            o<<d[i]<<" ";
    }
    f.close();
    o.close();
}