#include <iostream>
#include <vector>
#include <stdio.h>
#define MAXN     100000
#define MAXNOD   2000000

#define NOTASSIGNED -1001

using namespace std;

vector<int> graph[MAXN];
vector<int> cost[MAXN];
int c[MAXNOD + 1],d[MAXNOD];

int main(){
  int n,m,i,a,b,st,dr,gr,p,cs;
  FILE *fin, *fout;

  fin = fopen("bellmanford.in","r");
  fscanf(fin, "%d%d",&n,&m);
  for(i = 0; i < m; i ++){
    fscanf(fin, "%d%d%d", &a,&b,&p);
    a--;
    b--;
    graph[a].push_back(b);
    cost[a].push_back(p);
  }
  fclose(fin);

  //printf("%d",graph[1][0]);

  st = 0;
  dr = 1;
  c[0] = 0;

  for(i = 0; i < n; i ++){
    d[i] = NOTASSIGNED;
  }
  d[0] = 0;

  while(st < dr && st < n*n){
    for(i = 0; i < (int)graph[c[st]].size(); i ++){
      gr = graph[c[st]][i];
      cs = cost[c[st]][i];

      if(d[gr] > d[c[st]] + cs || d[gr] == NOTASSIGNED){
        d[gr] = d[c[st]] + cs;
        c[dr] = gr;
        dr++;
      }
    }

    st ++;
  }

  fout = fopen("bellmanford.out","w");
  if(st == n*n)
    fprintf(fout,"Ciclu negativ!\n");

  else{
    for(i = 1; i < n; i ++){
      fprintf(fout, "%d ",d[i]);
    }
    fprintf(fout, "\n");
  }

  fclose(fout);
  return 0;
}