#include <cstdio>
#include <queue>

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

const int Q=50002,INF=1000000000;

int nod,muc;

struct tipe{
    int to,cst;
};

std::vector<tipe> go[Q];

std::queue<int> v;

int cost[Q],ap[Q];

int main()
{
    fscanf(in,"%d%d",&nod,&muc);

    int a,b,c;

    for(int i=1; i<=muc; i++)
    {
        fscanf(in,"%d%d%d",&a,&b,&c);
        go[a].push_back(tipe{b,c});
    }

    for(int i=1; i<=nod; i++)
        cost[i]=INF;

    cost[1]=0;
    ap[1]=1;
    int start=0;

    v.push(1);

    int act;

    while(start<v.size())
    {
        act=v.front();
        v.pop();

        for(int i=0;i<go[act].size(); i++)
        {
            if(go[act][i].cst+cost[act] < cost[go[act][i].to])
            {
                cost[go[act][i].to]=go[act][i].cst+cost[act];

                ap[go[act][i].to]++;

                if(ap[go[act][i].to]==nod)
                {
                    fprintf(out,"Ciclu negativ!");
                    return 0;
                }

                v.push(go[act][i].to);
            }
        }
        start++;
    }

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

    return 0;
}