#include <bits/stdc++.h>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const int N=50010;
const int oo=1000000000;
bitset<N> inQ;
queue<int> q;
vector<pair<int,int>> v[N];
int n,m,d[N],cnt[N],x,y,z;
int main()
{
  f>>n>>m;
  for(;m;m--)
  {
      f>>x>>y>>z;
      v[x].push_back(make_pair(y,z));
  }
  fill(d+1,d+n+1,oo);
  int s=1;
  d[s]=0;
  inQ[s]=1;
  q.push(s);
  while(q.size())
  {
      int nod=q.front();
      q.pop();
      inQ[nod]=0;
      for(auto it:v[nod])
      {
          int vec,dvec;
          tie(vec,dvec)=it;
          if(d[vec]>d[nod]+dvec)
          {
              d[vec]=d[nod]+dvec;
              cnt[vec]++;
              if(cnt[vec]>n)
              {
                  g<<"Ciclu negativ";
                  return 0;
              }
              if(!inQ[vec])
              {
                  inQ[vec]=1;
                  q.push(vec);
              }
          }
      }
  }
  for(int i=2;i<=n;i++)
    g<<d[i]<<' ';
    return 0;
}