#include <cstdio>

using namespace std;

const int NMUC=250005,NNOD=50005,INF=50000005;
int nnod,nmuc,inod,imuc,iiter,x,y,cost;
int tat[NNOD],vdist[NNOD];

struct sct
{
    int x,y,cost;
} vmuc[NMUC];

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

    scanf ("%d%d",&nnod,&nmuc);

    for (imuc=1; imuc<=nmuc; ++imuc)
    {
        scanf ("%d%d%d",&x,&y,&cost);
        vmuc[imuc].x=x;
        vmuc[imuc].y=y;
        vmuc[imuc].cost=cost;
    }

    for (inod=2;inod<=nnod;++inod)
    {
        vdist[inod]=INF;
    }

    for (iiter=1; iiter < nnod; ++iiter)
    {
        for (imuc=1; imuc<=nmuc; ++imuc)
        {
            x=vmuc[imuc].x;
            y=vmuc[imuc].y;
            cost=vmuc[imuc].cost;

            if (vdist[x] +  cost < vdist[y])
            {
                vdist[y] = vdist[x] + cost;
                tat[y]=x;
            }
        }
    }

    for (imuc=1; imuc<=nmuc; ++imuc)
    {
        x=vmuc[imuc].x;
        y=vmuc[imuc].y;
        cost=vmuc[imuc].cost;

        if (vdist[x] +  cost < vdist[y])
        {
            printf ("Ciclu negativ!");
            return 0;
        }
    }

    for (inod=2;inod<=nnod;++inod)
    {
        printf("%d ",vdist[inod]);
    }

    return 0;
}