#include <bits/stdc++.h>
using namespace std;

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

int n, m;

struct nod{
  int vis;
  bool inq;
  int dist=(1<<30);
  vector<pair<int, int>> out;
};

vector<nod> g;

bool bellmanford(int start){
  queue<int> q;
  g[start].dist=0;
  q.push(start);
  g[start].vis++;
  g[start].inq=1;
  while(!q.empty()){
    int x=q.front(); q.pop();
    g[x].inq=0;
    for(auto it:g[x].out){
      if(g[it.first].dist>g[x].dist+it.second){
        g[it.first].dist=g[x].dist+it.second;
        if(!g[it.first].inq){
          g[it.first].vis++;
          if(g[it.first].vis==n) return 0;
          q.push(it.first);
        }
      }
    }
  }
  return 1;
}

int main(){
  fin>>n>>m;
  g.resize(n+1);
  for(int i=1;i<=m;++i){
    int a, b, c;
    fin>>a>>b>>c;
    g[a].out.push_back({b, c});
  }
  if(bellmanford(1)){
    for(int i=2;i<=n;++i) fout<<g[i].dist<<" ";
    fout<<"\n";
  }
  else fout<<"Ciclu negativ!\n";
}