#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

struct muchie{
  int a, b, cost;
};

int dist[50001], cnt[50001];
bool inq[50001];
vector <pair <int,int>> v[50001];
queue <int> q;

int main() {
  FILE *fin, *fout;
  int n, m, i, j, x, y, c, st, nr;
  fin=fopen("bellmanford.in","r");
  fout=fopen("bellmanford.out","w");
  fscanf(fin, "%d%d",&n,&m);
  for(i=1;i<=m;i++) {
    fscanf(fin, "%d%d%d",&x,&y,&c);
    v[x].push_back({y,c});
  }
  for(i=1;i<=n;i++)
    dist[i]=1000000000;
  dist[1]=0;
  q.push(1);
  inq[1]=1;
  cnt[1]++;
  nr=1;
  while(q.size()!=0 && nr<=n*m) {
    x=q.front();
    nr++;
    for(i=0;i<v[x].size();i++) {
      if(dist[x]+v[x][i].second<dist[v[x][i].first]) {
        dist[v[x][i].first]=dist[x]+v[x][i].second;
        if(inq[v[x][i].first]==0) {
          q.push(v[x][i].first);
          inq[v[x][i].first]=1;
          cnt[v[x][i].first]++;
          if(cnt[v[x][i].first]>n) {
            fprintf(fout, "Ciclu negativ!");
            return 0;
          }
        }
      }
    }
    inq[x]=0;
    q.pop();
  }
  for(i=2;i<=n;i++)
    fprintf(fout, "%d ",dist[i]);
  fclose( fin );
  fclose( fout );
  return 0;
}