#include <iostream>
#include <fstream>
#include <deque>
#include <vector>
#define inf 1000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int m, n, x, y, c, cn;
struct much{
int x, y, c;
};
vector<much> la;
vector<int> d;

void citire(){
f>>n>>m;
la.resize(m);
for(int i=0; i<m; ++i){
    f>>la[i].x>>la[i].y>>la[i].c;
    }
}

void bf(int x)
{
d[x] = 0;
   for (int i=0; i<n; ++i)
      for (int j=0;j<m;++j)
          if (d[la[j].x]+la[j].c<d[la[j].y])
			d[la[j].y]=d[la[j].x]+la[j].c;

}

int main()
{
    citire();
    d.resize(n+1);
    for(int i=0; i<=n; ++i)
        d[i]=inf;
    bf(1);
    for (int j=0;j<m;++j)
          if (d[la[j].x]+la[j].c<d[la[j].y]){
            cn=1; break;
          }

    if(cn) {g<<"Ciclu negativ!"<<'\n'; return 0;}
    for(int i=1; i<=n; ++i)
            if(i!=1) g<<d[i]<<' ';
    g.close();
    return 0;
}