#include <fstream>

using namespace std;
int mat[1001][1001][3];
int costmin[1001],coada[1001];
int main()
{
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,i,m,st=0,dr=1,obs=0;
f>>n>>m;
for(i=1;i<=n;i++)
                costmin[i]=999999999;
int x,y,c;
while(f>>x>>y>>c)
                {
                mat[x][y][0]=1;
                mat[x][y][1]=c;
                }
costmin[1]=0;
coada[0]=1;
while(st<dr)
           {
           int a=coada[st];
           for(i=1;i<=n;i++)
                           if(mat[a][i][0]==1&&mat[a][i][1]+costmin[a]<costmin[i])
                                                                                 {
                                                                                 costmin[i]=mat[a][i][1]+costmin[a];
                                                                                 mat[a][i][2]++;
                                                                                 if(mat[a][i][2]==n)
                                                                                                   {
                                                                                                   obs=1;
                                                                                                   i=n+1;
                                                                                                   st=dr;
                                                                                                   }
                                                                                 coada[dr]=i;
                                                                                 dr++;
                                                                                 }
           st++;
           }
if(obs==0)
          for(i=2;i<=n;i++)
                {
                if(costmin[i]!=999999999)
                                     g<<costmin[i]<<" ";
                else
                    g<<"-1 ";
                }
else
    g<<"Ciclu negativ!";
return 0;
}