#include <bits/stdc++.h>
using namespace std;

#define INF 0x3f3f3f3f
queue <int> q;
vector <int> G[50100],C[50100];


int d[50100],ciclu[50100],x,y,c,m,n;

int bell(int x0)
{
    for(int i=2;i<=n;i++)
        d[i]=INF;
        d[x0]=0;

     q.push(x0);

    while(!q.empty()){
        x = q.front();

        ciclu[x]++;
        if(ciclu[x]>n)
                return -1;

        for(int i=0;i<G[x].size();i++)
            if(d[G[x][i]] > d[x] + C[x][i])
        {
            d[G[x][i]] = d[x] + C[x][i];
            q.push(G[x][i]);
        }
        q.pop();
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i=2;i<=n;i++)
        d[i]=INF;

    while(m--){
        scanf("%d%d%d",&x,&y,&c);
        G[x].push_back(y);
        C[x].push_back(c);

    }

   int c=bell(1);
    if(c)
        for(int i=2;i<=n;i++)
                printf("%d ",d[i]);

    else printf("Ciclu negativ!");
    return 0;
}