#include <fstream>
#include <queue>
#include <vector>
#define INF 10000000
#define NMAX 50002

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");


struct arc{int vf,c;};
vector<arc> g[NMAX];
int n,m,start=1;
int cmin[NMAX];
int nr[NMAX];
bool circuitneg=0;
queue<int> c;
int main()
{ int x,i,y,cost;
  arc a;

  fin>>n>>m;
  for(i=0;i<m;i++)
  {
    fin>>x>>y>>cost;
    a.vf=y;
    a.c=cost;
    g[x].push_back(a);
  }
  for(i=1;i<=n;i++) cmin[i]=INF;
  cmin[start]=0;
  c.push(start);


  for(i=1;i<=n;i++) cmin[i]=INF;
  cmin[start]=0;
  c.push(start);
  while(!c.empty() && !circuitneg)
  {
    x=c.front(); c.pop();
    ///par urg lista adiacenta a lui x
    for(i=0;i<g[x].size();i++)
    {
      y=g[x][i].vf; cost=g[x][i].c;
      if(cmin[y]>cmin[x]+cost)
      {
        cmin[y]=cmin[x]+cost;
        nr[y]++;
          if(nr[y]==n) circuitneg=1;
            else c.push(y);
      }
    }
  }
  if (!circuitneg)
    for (i=2; i<=n; i++) fout<<cmin[i]<<' ';
    else fout<<"Ciclu negativ!";
    return 0;
}