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