#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF (1<<30)
using namespace std;

struct node
{
    int x,c;
};
vector<node>v[NMAX];
int d[NMAX],viz[NMAX],nr[NMAX];
int n,m,i,j,x,y,c,e,fiu;
queue<int>q;
node pp(int a,int b)
{
    node X;X.x=a;X.c=b;
    return X;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i) d[i]=INF;
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].push_back(pp(y,c));
    }
    viz[1]=1;d[1]=0;
    q.push(1);e=0;
    while(!q.empty())
    {
        int x=q.front();
        viz[x]=0;
        q.pop();
        for(i=0;i<v[x].size();++i)
        {
            fiu=v[x][i].x;
            c=v[x][i].c;
            if(d[fiu] > d[x] + c)
            {
                d[fiu]=d[x]+c;
                if(viz[fiu] == 0)
                {
                    if(nr[fiu] >n)  e=1;
                        else
                        {
                        q.push(fiu);
                        viz[fiu]=1;
                        ++nr[fiu];
                        }
                }
            }
        }
    }
    if(e == 0)
    {
        for(i=2;i<=n;++i)
            if (d[i] != INF) printf("%d ",d[i]);
                else printf("0 ");
    }
    else printf("Ciclu negativ!\n");
    return 0;
}