#include<fstream>
#include<deque>
#include<vector>
#define INF 2000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int x,y,z,i,n,m,j,f[50005],d[50005],nr[50005],nod,vecin;
vector< pair<int,int> > v[50005];
deque<int> c;
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>x>>y>>z;
        v[x].push_back(make_pair(y,z));
    }
    for(i=1;i<=n;i++){
        f[i]=0;
        d[i]=INF;
    }
    d[1]=0;
    f[1]=1;
    nr[1]=1;
    c.push_back(1);
    while( !c.empty() ){
        nod=c[0];
        for(i=0;i<v[nod].size();i++){
            vecin=v[nod][i].first;
            if(d[vecin]>d[nod]+v[nod][i].second){
                d[vecin]=d[nod]+v[nod][i].second;
                if(f[vecin]==0){
                    nr[vecin]++;
                    if(nr[vecin]>=n){
                        fout<<"Ciclu negativ\n";
                        return 0;
                    }
                    c.push_back(vecin);
                    f[vecin]=1;
                }
            }
        }
        c.pop_front();
        f[nod]=0;
    }
    for(i=2;i<=n;i++){
        fout<<d[i]<<" ";
    }
    return 0;
}