#include <fstream>
const int M=250000;
const int N=50000;
const int MAX=999999;
using namespace std;
struct graf{int x,y,cost;}v[M];
int n,m,d[N];
int bford()
{ int i;
    d[1]=0;
    for( i=2;i<=n;i++)
      d[i]=MAX;
    for(i=1;i<n;i++)
      for(int j=1;j<=m;j++)
        if(d[v[j].y]>d[v[j].x]+v[j].cost)
           d[v[j].y]=d[v[j].x]+v[j].cost;
    for(int j=1;j<=m;j++)
      if(d[v[j].y]>d[v[j].x]+v[j].cost)
        return 0;
return 1;
}
int main()
{
    fstream f("bellmanford.in",ios::in);
    fstream g("bellmanford.out",ios::out);
    f>>n>>m;
    for(int i=1;i<=m;i++)
         f>>v[i].x>>v[i].y>>v[i].cost;
    if(bford()==0)
     g<<"Ciclu negativ!";
    else
     for(int j=2;j<=n;j++)
      g<<d[j]<<" ";

    return 0;
}