#include <fstream>
#define DIM 50001
#include <vector>
#include <algorithm>

using namespace std;

struct edge
{
    int next, cost;
};

edge temp;

vector <edge> nod[DIM];

int d[DIM], n, a, b, c, m, vfc, vis[DIM], urm, cycle, x;

long int step;

vector <int> v;

bool comp(const int &e, const int &f)
{
    return d[e]>d[f];
}

int check()
{
    for(int i=1; i<=n; ++i)
    {
        for(int j=0; j<nod[i].size(); ++j)
        {
            if(d[nod[i][j].next]>d[i]+nod[i][j].cost)
                return 1;
        }
    }
    return 0;
}

int main()
{
    ifstream in("bellmanford.in");
    ofstream out ("bellmanford.out");
    in>>n>>m;
    x=m;
    while(x--)
    {
        in>>a>>b>>c;
        temp.next=b; temp.cost=c;
        nod[a].push_back(temp);
    }
    v.push_back(1);
    make_heap(v.begin(), v.end(), comp);
    step=0;
    while(v.size()&&step<=((long long)n*m))
    {
        step++;
        pop_heap(v.begin(), v.end(), comp);
        vfc=v.back();
        v.pop_back();
        vis[vfc]=0;
        for(int i=0; i<nod[vfc].size(); ++i)
        {
            urm=nod[vfc][i].next;
            if(vis[urm]==0&&(d[urm]>d[vfc]+nod[vfc][i].cost||d[urm]==0))
            {
                vis[urm]=1;
                d[urm]=d[vfc]+nod[vfc][i].cost;
                v.push_back(urm);
                push_heap(v.begin(), v.end(), comp);
            }
        }
    }
    if(check())
        out<<"Ciclu negativ!";
    else
        for(int i=2; i<=n; ++i)
            out<<d[i]<<" ";
    out<<"\n";
    in.close();
    out.close();
    return 0;
}