#include <cstdio>
#include <fstream>
#include <cstring>
#include <queue>
#define Nmx 50001
#define INF 0x3f3f3f3f

using namespace std;

int cost[Nmx],cnt[Nmx],viz[Nmx],n,m;
struct nod { int inf,c;nod *urm;};
nod *G[Nmx];
queue <int> Q;

ifstream fin("bellmanford.in");

void add(int x,int y,int cst)
{
    nod *aux=new nod;
    aux->inf = y;
    aux->c = cst;
    aux->urm = G[x];
    G[x]=aux;
}

void read()
{
    fin>>n>>m;
    int x,y,c;
    for(;m;--m)
    {
        fin>>x>>y>>c;
        add(x,y,c);
    }
}

int solve()
{
    for(int i=2;i<=n;++i)
        cost[i]=INF;
    Q.push(1);
    viz[1]=1;
    while(!Q.empty())
    {
        int x=Q.front();
        Q.pop();
        viz[x]=0;
        for(nod *p=G[x];p;p=p->urm)
            if(cost[p->inf]>cost[x]+p->c)
            {
                cost[p->inf]=cost[x]+p->c;
                cnt[p->inf]++;
                if(cnt[p->inf]>n) return 1;
                if(!viz[p->inf])
                {
                    viz[p->inf]=1;
                    Q.push(p->inf);
                }
            }
    }
    return 0;
}

int main()
{
    freopen("bellmanford.out","w",stdout);
    read();
    if(solve())
        printf("Ciclu negativ!");
    else for(int i=2;i<=n;++i)
            if(cost[i]==INF) printf("0");
            else printf("%d ",cost[i]);
    printf("\n");
    return 0;
}