#include <iostream>
#include <cstdio>
#include <queue>
#define INF 1e9
using namespace std;
const int MMAX = 250001;
const int NMAX = 50001;
int distanta[NMAX];
int ap[NMAX];
bool in_queue[NMAX];
vector <pair<int,int> > G[NMAX];
queue <int> Q;
int main()
{
    FILE *fin, *fout;
    int n,m,i,x,y,w,nod,p;
    fin=fopen("bellmanford.in","r");
    fout=fopen("bellmanford.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(fin,"%d %d %d",&x,&y,&w);
        G[x].push_back(make_pair(y,w));
    }
    for(i=2;i<=n;i++)
        distanta[i] = INF, ap[i] = 0, in_queue[i] = false;
    in_queue[1] = true;
    Q.push(1);
    while(!Q.empty() && ap[Q.front()] < n){
        nod = Q.front();
        in_queue[nod] = false;
        Q.pop();
        for(p=0;p<G[nod].size();p++)
            if(distanta[nod] + G[nod][p].second < distanta[G[nod][p].first]){
                distanta[G[nod][p].first] = distanta[nod] + G[nod][p].second;
                ap[G[nod][p].first] ++;
                if(in_queue[G[nod][p].first] == false){
                    Q.push(G[nod][p].first);
                    in_queue[G[nod][p].first] = true;
                }
            }
    }
    if(!Q.empty())
        fprintf(fout,"Ciclu negativ!");
    else
        for(i=2;i<=n;i++)
            fprintf(fout,"%d ",distanta[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}