#include <fstream>
#include <vector>
#include <set>
#define DIM 50001
#define INF 0x3f3f3f3f
using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

struct muchie
{
    long price; long dest;
};

muchie temp;

vector <muchie> node[DIM];

struct stare
{
    long place, way;
};

struct classcomp
{
    bool operator () (const stare &A, const stare &B) const
    {
        if(A.way!=B.way)
            return A.way<B.way;
        else return A.place<B.place;
    }
};

set <stare, classcomp> bf;

set <stare, classcomp> :: iterator it;

stare temp1, temp2;

long n, m, best[DIM];

void bellmanford()
{
    long long step=0;
    long vfc, drum;
    temp1.place=1; temp1.way=0;
    best[1]=0;
    bf.insert(temp1);
    while(step<=(long long)n*m&&bf.size())
    {
        it=bf.begin();
        temp1=*it;
        bf.erase(it);
        step++;
        vfc=temp1.place;
        drum=temp1.way;
        for(long i=0; i<node[vfc].size(); ++i)
        {
            temp=node[vfc][i];
            if(temp.price+drum<best[temp.dest])
            {
                temp2.place=temp.dest;
                temp2.way=best[temp.dest];
                it=bf.find(temp2);
                if(it!=bf.end())
                    bf.erase(it);
                temp2.way=temp.price+drum;
                best[temp.dest]=temp2.way;
                bf.insert(temp2);
            }
        }
    }
}

void initialize()
{
    for(long i=2; i<=n; ++i)
    {
        best[i]=INF;
    }
}

long check()
{
    for(long i=1; i<=n; ++i)
    {
        for(long j=0; j<node[i].size(); ++j)
        {
            temp=node[i][j];
            if(temp.price+best[i]<best[temp.dest])
            {
                return 1;
                goto p;
            }
        }
    }
    return 0;
    p: ;
}


int main()
{
    in>>n>>m;
    for(long i=1; i<=m; ++i)
    {
        long x, y, cost;
        in>>x>>y>>cost;
        temp.price=cost;
        temp.dest=y;
        node[x].push_back(temp);
    }
    initialize();
    bellmanford();
    if(check())
    {
        out<<"Ciclu negativ!\n";
    }
    else
    {
        for(long i=2; i<=n; ++i)
            out<<best[i]<<" ";
        out<<"\n";
    }
    in.close();
    out.close();
    return 0;
}