#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <bitset>
#define INF 2147000000
using namespace std;
struct muchie{int x,y,z;}a[50005];
int *v[50005],*c[50005],*r[50005];
int g[50005], d[50005];
bitset <50005> iq;
bitset <250005> mark;   
queue<int>Q;


int main(){
  int n,m,i,x,y,z,nod,fiu;
  freopen("bellmanford.in","r",stdin);
  freopen("bellmanford.out","w",stdout);
  ////////////////
  scanf("%d %d", &n,&m);
  for (i=1;i<=m;++i){
    scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].z);
    g[a[i].x]++;//g[a[i].y]++;
  }
  for (i=1;i<=n;++i){
    v[i]=(int*)malloc(sizeof(int)*(g[i]+1));
    c[i]=(int*)malloc(sizeof(int)*(g[i]+1));
    r[i]=(int*)malloc(sizeof(int)*(g[i]+1));
    g[i]=0;
  }
  for (i=1;i<=m;++i){
    x=a[i].x;y=a[i].y;z=a[i].z;
    v[x][g[x]]=y; c[x][g[x]]=z; r[x][g[x]++]=i;
    //v[y][g[y]]=x; c[y][g[y]]=z; r[y][g[y]++]=i;
  }
  /////////////
  for (i=2;i<=n;++i)d[i]=INF;
  d[1]=0; Q.push(1); iq[1]=1;
  while (!Q.empty()){
    nod=Q.front(); Q.pop(); iq[nod]=0;
    for (i=0;i<g[nod];++i){
      fiu=v[nod][i];
      if (d[nod]+c[nod][i]<d[fiu]){
        d[fiu]= d[nod] + c[nod][i];
        if (!iq[fiu]){
          Q.push(fiu); iq[fiu]=1;
          if (mark[r[nod][i]]){printf("Ciclu negativ!\n");exit(0);}
          else mark[r[nod][i]]=1;
        }
      }
    }
  }
  for (i=2;i<=n;++i)printf("%d ",d[i]);

return 0;
}