#include<stdio.h>
#include<queue>
#include<vector>
#define inf 1<<30
using namespace std;
int i,n,ok,x,y,g,w[50005],f[50005],m,k;
struct str
{

    int x,g;
    str(int xx=0,int gg=0)
    {

        x=xx;
        g=gg;
    }
};
vector<str> v[50005];
queue<int> q;
int main()
{

    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        w[i]=inf;
    for(i=1;i<=m;i++)
    {

        scanf("%d%d%d",&x,&y,&g);
        v[x].push_back(str(y,g));

    }
    w[1]=0;
    q.push(1);
    while(!q.empty()&&ok==0)
    {
        k=q.front();
        q.pop();
        f[k]++;
        if(f[k]>=n)
            ok=1;
        for(i=0;i<v[k].size();i++)
        {
            if(w[k]+v[k][i].g<w[v[k][i].x])
            {
                w[v[k][i].x]=w[k]+v[k][i].g;
                q.push(v[k][i].x);

            }

        }
    }
    if(ok==1)
        printf("Ciclu negativ!");
    else
        for(i=2;i<=n;i++)
            printf("%d ",w[i]);
    return  0;
}