#include<fstream>
#include<vector>
#include<queue>

using namespace std;

#define NMAX 50003
#define MMAX 250003
#define INF 1000000000

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

int n,m,i,j,a,b,c,nq,x,s;
int cost[NMAX],e[2][NMAX];
vector< pair<int,int> > v[NMAX];
queue<int> q[2];

int main() {
  fi>>n>>m;
  for(i=1;i<=m;i++) {
    fi>>a>>b>>c;
    v[a].push_back(make_pair(b,c));
  }
  fi.close();
  for(i=2;i<=n;i++) cost[i]=INF;
  q[nq].push(1);
  e[nq][1]=1;
  for(i=1;i<=n;i++) {
    while(!q[nq].empty()) {
      x=q[nq].front();
      q[nq].pop();
      e[nq][x]=0;
      for(j=0,s=v[x].size();j<s;j++)
       if(cost[x]+v[x][j].second<cost[v[x][j].first]) {
         cost[v[x][j].first]=cost[x]+v[x][j].second;
         if(!e[1-nq][v[x][j].first]) {
           q[1-nq].push(v[x][j].first);
           e[1-nq][v[x][j].first]=1;
         }
       }
    }
    nq=1-nq;
  }
  for(i=1;i<=n;i++)
   for(j=0,s=v[i].size();j<s;j++)
    if(cost[i]+v[i][j].second<cost[v[i][j].first]) {
      fo<<"Ciclu negativ!\n";
      fo.close();
      return 0;
    }
  for(i=2;i<=n;i++) fo<<cost[i]<<" ";
  fo<<"\n";
  fo.close();
  return 0;
}