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

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

long best[DIM], added[DIM], n, m;

struct muchie
{
    long price, dest;
};

muchie temp1;

vector <muchie> node[DIM];

queue <int> q;

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

void bellmanford()
{
    long long step;
    long vfc;
    q.push(1);
    while(!q.empty()&&step<=1LL*n*m)
    {
        vfc=q.front();
        q.pop();
        added[vfc]=0;
        for(int i=0; i<node[vfc].size(); ++i)
        {
            temp1=node[vfc][i];
            step++;
            if(temp1.price+best[vfc]<best[temp1.dest])
            {
                best[temp1.dest]=temp1.price+best[vfc];
                if(!added[temp1.dest])
                    q.push(temp1.dest);
            }
        }
    }
}

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


int main()
{
    in>>n>>m;
    for(int i=1; i<=m; ++i)
    {
        long x, y, cost;
        in>>x>>y>>cost;
        temp1.price=cost;
        temp1.dest=y;
        node[x].push_back(temp1);
    }
    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;
}