#include <stdio.h>
#define MAX_M 250000
#define MAX_N 50000
#define INF 1001
using namespace std;
bool f[MAX_N+1];
int l[MAX_M+1], next[MAX_M+1], p[1+MAX_N], cost[MAX_M+1], scor[1+MAX_N], q[MAX_M], st, dr, tata[MAX_M+1], mod[MAX_N+1];

void addmuchii(int nod){
  int muchie=p[nod];
  while(muchie!=0){
    if(!f[muchie]){
      f[muchie]=true;
      dr++;
      q[dr%MAX_M]=muchie;
    }
    muchie=next[muchie];
  }
}

int main()
{
  int n, m, a, b, i, pret, muchie;
  FILE *fi=fopen("bellmanford.in", "r"), *fo=fopen("bellmanford.out", "w");
  fscanf(fi, "%d%d", &n, &m);
  for(i=1;i<=m;i++){
    fscanf(fi, "%d%d%d", &a, &b, &cost[i]);
    next[i]=p[a];
    p[a]=i;
    l[i]=b;
    tata[i]=a;
    mod[b]++;
  }
  for(i=1;i<=n;i++)
    scor[i]=INF;
  st=dr=0;
  scor[1]=0;
  addmuchii(1);
  st++;
  bool ciclu=false;
  while(!ciclu && st<=dr){
    muchie=q[st%MAX_M];
    pret=scor[tata[muchie]]+cost[muchie];
    if(pret<scor[l[muchie]]){
      scor[l[muchie]]=pret;
      addmuchii(l[muchie]);
      mod[l[muchie]]--;
      if(mod[l[muchie]]<0)
        ciclu=true;
    }
    f[muchie]=false;
    st++;
  }
  if(ciclu)
    fprintf(fo, "Ciclu negativ!");
  else
    for(i=2;i<=n;i++)
      fprintf(fo, "%d ", scor[i]);
  fclose(fi);
  fclose(fo);
  return 0;
}