#include<cstdio>
#define nmax 5001
#define infinit 100000

using namespace std;

int n,m;
int c[nmax][nmax];
int d[nmax];


void citire()
{
    int i,j,x,y,cost;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
         c[i][j]=infinit;
    for(i=2;i<=n;i++)
      d[i]=infinit;
    for(i=1;i<=m;i++)
      {
          scanf("%d%d%d",&x,&y,&cost);
          c[x][y]=cost;
      }
}

int bellman_ford()
{
    int i,j,k;
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        for(k=1;k<=n;k++)
          if(c[j][k]!=infinit && d[k]>d[j]+c[j][k])
            d[k]=d[j]+c[j][k];
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(d[j]>d[i]+c[i][j]) return 0;
    return 1;
}

void afisare()
{
    for(int i=2;i<=n;i++)
      printf("%d ",d[i]);
    printf("%c",'\n');
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    citire();
    if(bellman_ford()==0)
       printf("Ciclu negativ!");
       else
         afisare();
    return 0;
}