#include <cstdio>
#include <vector>
#include <queue>
#define pb push_back

using namespace std;

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


struct sct
{
    int y,cost;
};
vector <sct> lst[NNOD];
queue <int> qu;

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

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

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

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

    qu.push(1);

    while(!qu.empty())
    {
        x=qu.front();
        qu.pop();
        inq[x]=0;
        nvec=lst[x].size();

        for (ivec=0;ivec<nvec;++ivec)
        {
            y=lst[x][ivec].y;
            cost=lst[x][ivec].cost;

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

                if (nrepl[y]==nnod)
                {
                    printf("Ciclu negativ!");
                    return 0;
                }

                if (!inq[y])
                {
                    qu.push(y);
                    inq[y]=1;
                }
            }
        }
    }

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


    return 0;
}