#include <cstdio>
#include <queue>

FILE* in=fopen("bellmanford.in","r");
FILE* out=fopen("bellmanford.out","w");

const int Q=250008,W=50007,INF=2000000000;

int lst[Q],val[2*Q],cost[2*Q],nxt[2*Q],nr;

void add(int a, int b, int c)
{
    nr++;
    val[nr]=b;
    cost[nr]=c;
    nxt[nr]=lst[a];
    lst[a]=nr;
}

int n,m;

int d[W],ap[W];

struct tipe
{
    int nod,val;
};

std::queue<tipe> q;

int main()
{
    fscanf(in,"%d%d",&n,&m);

    int a,b,c;

    for(int i=1; i<=m; i++)
    {
        fscanf(in,"%d%d%d",&a,&b,&c);

        add(a,b,c);
    //    add(b,a,c);
    }

    for(int i=2; i<=n; i++)
        d[i]=INF;

    q.push(tipe{1,0});

    ap[1]=1;

    tipe act;

    while(!q.empty() )
    {
        act=q.front();
        q.pop();

        if(act.val!=d[act.nod])
            continue;

        for(int p=lst[act.nod]; p; p=nxt[p])
        {
            if(d[val[p]] > act.val+cost[p])
            {
                ap[val[p]]++;

                if(ap[val[p]]==n)
                {
                    fprintf(out,"Ciclu negativ!");
                    return 0;
                }

                d[val[p]]=act.val+cost[p];
                q.push(tipe{val[p],d[val[p]]});
            }
        }
    }

    for(int i=2; i<=n; i++)
        fprintf(out,"%d ",d[i]);

    return 0;
}