#include <bits/stdc++.h>
#define NMAX 50002
#define INF 1e9+2

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct arc{int vf,c;};
int start = 1;
vector <arc> g[NMAX];
queue<int> q;
int cmin[NMAX];
int nr[NMAX];
bool ok = 1;
int n,m;
int main()
{
    int i,x,y,cost,c;
    fin>>n>>m;
    arc v;
    for(i=1;i<=m;i++){
        fin>>x>>y>>cost;
        v.vf = y;
        v.c = cost;
        g[x].push_back(v);
    }
    for(i=1;i<=n;i++){
        cmin[i] = INF;
    }
    q.push(start);
    //nr[start] = 1;
    cmin[start] = 0;
    while(!q.empty()&&ok){
        x = q.front();
        q.pop();
        for(i=0;i<g[x].size();i++){
            y = g[x][i].vf;
            c = g[x][i].c;
            if(cmin[x]+c<cmin[y]){
                nr[y]++;
                cmin[y] = cmin[x]+c;
                if(nr[y]==n){
                    ok = 0;
                }
                else{
                    q.push(y);
                }
            }
        }
    }
    if(ok){
        for(i=2;i<=n;i++){
            fout<<cmin[i]<<' ';
        }
    }
    else{
        fout<<"Ciclu negativ!";
    }
    return 0;
}