#include <cstdio>
#define max 250010

using namespace std;

struct muchie{int x,y,cost;} a[max];
int d[50001],ok,n,m;

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].cost);
        if(a[i].x==1)
            d[a[i].y]=a[i].cost;
    }
    for(int i=2;i<=n;i++)
        if(d[i]==0)
            d[i]=max;
    int ok=0;
    for(int i=1;i<=m;i++)
       if(d[a[i].x]+a[i].cost<d[a[i].y])
            ok=1;
    if(ok==1)
        printf("Ciclu negativ!\n");
    else
    {
    while(ok==0)
    {
        ok=1;
        for(int i=1;i<=m;i++)
            if(d[a[i].y]>d[a[i].x]+a[i].cost)
            {
                d[a[i].y]=d[a[i].x]+a[i].cost;
                ok=0;
            }
    }
    for(int i=2;i<=n;i++)
    {
        if(d[i]==max)
            printf("0 ");
        else
            printf("%d ",d[i]);
    }
    }
    return 0;
}