#include <stdio.h>
#include <stdlib.h>
#define MAXN 50000
#define MAXM 250000
#define MAXQU 65536
#define INF 2000000000

int lst[MAXN+1], vf[MAXM+1], next[MAXM+1], cost[MAXM+1], queue[MAXQU], inq[MAXN+1], dist[MAXN+1], tim[MAXN+1];

int main()
{
    FILE *fin, *fout;
    int n, m, i, x, y, c, b, e;
    fin=fopen("bellmanford.in", "r");
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=m; i++){
      fscanf(fin, "%d%d%d", &x, &y, &c);
      vf[i]=y;
      cost[i]=c;
      next[i]=lst[x];
      lst[x]=i;
    }
    fclose(fin);
    for(i=2; i<=n; i++)
      dist[i]=INF;
    b=0; e=queue[b]=tim[1]=1;
    while(b!=e && tim[queue[b]]<n){
      x=queue[b];
      b=(b+1)&(MAXQU-1);
      inq[x]=0;
      y=lst[x];
      while(y){
        if(dist[vf[y]]>dist[x]+cost[y]){
          dist[vf[y]]=dist[x]+cost[y];
          if(inq[vf[y]]==0){
            tim[vf[y]]++;
            inq[vf[y]]=1;
            queue[e]=vf[y];
            e=(e+1)&(MAXQU-1);
          }
        }
        y=next[y];
      }
    }
    fout=fopen("bellmanford.out", "w");
    if(b!=e)
      fprintf(fout, "Ciclu negativ!");
    else
      for(i=2; i<=n; i++)
        if(dist[i]==INF)
          fprintf(fout, "0 ");
        else
          fprintf(fout, "%d ", dist[i]);
    fprintf(fout, "\n");
    fclose(fout);
    return 0;
}