#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define dim 50005
#define INF 0x3f3f3f3f
#define x first
#define y second
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,i,m,d[dim],viz[dim],a,b,c,s,f[dim];
queue<int> q;
vector< pair<int,int> > v[dim];
int main(){
    fin>>n>>m;
    for(i=1;i<=m;i++){
        fin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
    }
    q.push(1);
    memset(d,INF,sizeof(d));
    d[1]=0;
    while(!q.empty()){
        s=q.front();
        viz[s]=1;
        for(i=0;i<v[s].size();i++){
            if(d[v[s][i].x]>d[s]+v[s][i].y){
                d[v[s][i].x]=d[s]+v[s][i].y;
                if(viz[v[s][i].x]==0){
                    q.push(v[s][i].x);
                    viz[v[s][i].x]=1;
                    f[s]++;
                    if(f[s]>=n){
                        fout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }

        }
        viz[s]=0;
        q.pop();
    }
    for(i=2;i<=n;i++){
        fout<<d[i]<<" ";
    }


    return 0;
}