//Drumuri minime de la varful s la oricare varf i - graful avand si arce de cost negativ

#include <cstdlib>
#include <fstream>
#define INF 250000001

using namespace std;

ofstream g("bellmanford.out");
int c[5001][5001],d[2500001],use[5001],n,m;

void citire()
{ifstream f("bellmanford.in");
 int i,j,x,y,cost;
 f>>n>>m;
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
    if(i==j) c[i][j]=0;
    else c[i][j]=INF;
  for(i=1;i<=m;i++)
    {f>>x>>y>>cost;
     c[x][y]=cost;
    }
f.close();
}

void bellman()
{ int i,j,x,min,k;

  for(i=1;i<=n;i++) d[i]=INF;
  d[1]=0;

  for(k=1; k<=n; k++)
   {min=INF;
    for(i=1;i<=n;i++)
     if(!use[i] && d[i]<min)
       {min=d[i];
        x=i;
       }

    if (min==INF) break;
    use[x]=1;

    for (i=1;i<=n;i++)
      if (!use[i] && d[x] + c[x][i] < d[i])
        d[i] = d[x] + c[x][i];

   //g<<x<<": ";for (i=1;i<=n;i++) g<<d[i]<<" ";g<<endl;
   }
   for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
      if (c[j][i]!=INF && i!=j && d[j] + c[j][i] < d[i])
        { g<<"Ciclu negativ!";
          exit(0);
        }
}

int main()
{ citire();
  bellman();
  for (int i=2;i<=n;i++)
    g<<d[i]<<" ";

  g.close();
  return 0;
}