#include<fstream>
#include<vector>
#include<queue>
#define inf  0x3f3f3f
#define dim 50005
#include<iostream>

using namespace std;

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

struct rtt
{
    int n,c;

};

vector <vector<rtt> > a(dim);
vector <int> d(dim,inf);
queue <int> q;

int nn,m;

void citire()
{
  int x0,y0,cc;

    in>>nn;
    in>>m;
    for (int i=1;i<=m;++i)
     {
         in>>x0>>y0>>cc;
         a[x0].push_back((rtt){y0,cc});
     }
}

int bell(int nod)
{
    q.push(nod);
    d[nod]=0;

    while (!q.empty())
    {
        nod=q.front();
        for (int i=0;i<a[nod].size();++i)
          if (d[a[nod][i].n]>d[nod]+a[nod][i].c)
            d[a[nod][i].n]=d[nod]+a[nod][i].c , q.push(a[nod][i].n);

            else
            if (d[a[nod][i].n]>0 && d[nod]<0)
             return 0;
             q.pop();
    }


}


int main()
{
    citire();

    bell(1);
    if (!bell(1))
     out<<"Ciclu negativ!";
     else
{
    for (int i=2;i<=nn;++i)
      if (d[i]!=inf) out<<d[i]<<" ";
       else out<<0;
}

    return 0;
}