#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

FILE*f=fopen("bellmanford.in","r");
FILE*h=fopen("bellmanford.out","w");

struct costul{
    int x,c;
};

vector<costul> v[50001];

queue<int> q;

int d[50001],p[50001],fl=1,n,m;

void bellmanford(){
    while ( !q.empty() ){
        int x=q.front();
        p[x]++;
        if ( p[x]==m ){fprintf(h,"Ciclu negativ!");fl=0;return;}
        q.pop();
        for ( int i=0;i<v[x].size();++i ){
            costul y=v[x][i];
            if ( (d[y.x]>=d[x]+y.c) || d[y.x]==-2000000000 ){
                d[y.x]=d[x]+y.c;
                q.push(y.x);
            }
        }
    }
}

int main()
{
    fscanf(f,"%d%d",&n,&m);
    for ( int i=1;i<=n;++i )
        d[i]=-2000000000;
    for ( int i=1;i<=m;++i ){
        int a,b,c;
        fscanf(f,"%d%d%d",&a,&b,&c);
        v[a].push_back({b,c});
    }
    d[1]=0;
    q.push(1);
    bellmanford();
    if ( fl==1 )
        for ( int i=2;i<=n;++i )
            fprintf(h,"%d ",d[i]);
    return 0;
}