#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct data{

int dest;
int cost;

};

vector <data> v[50005];

int cost[50005];

bool verificat[50005];
queue <int> coada_verificati;


int main()
{
   int n,m,a,b,c,i,j1,j2;

   fin>>n>>m;

   for(i=1;i<=m;i++)
   {
       data adaugare;

       fin>>a>>b>>c;

       adaugare.cost=c;
       adaugare.dest=b;

       v[a].push_back(adaugare);

   }

   for(i=2;i<=n;i++)
    cost[i]=1005;

   for(i=1;i<n;i++)
   {
       for(j1=1;j1<=n;j1++)
        if(verificat[j1]==0 && cost[j1]!=1005 )
            for(j2=0;j2<v[j1].size();j2++)
            {
                if( cost[j1] + v[j1][j2].cost < cost[ v[j1][j2].dest ]  )
                {
                    cost[ v[j1][j2].dest ]= cost[j1] + v[j1][j2].cost ;
                }
                else
                {
                    verificat[ v[j1][j2].dest ] =1;
                    coada_verificati.push( v[j1][j2].dest );
                }


            }

        while(!coada_verificati.empty())
        {
            verificat[ coada_verificati.front() ]=0;
            coada_verificati.pop();

        }


   }

   // vreificare ciclu negativ;

   for(j1=1;j1<=n;j1++)
        if(verificat[j1]==0)
            for(j2=0;j2<v[j1].size();j2++)
            {
                if( cost[j1] + v[j1][j2].cost < cost[ v[j1][j2].dest ]  )
                {
                    fout<<"Ciclu negativ!";
                    return 0;
                }
                else
                {
                    verificat[ v[j1][j2].dest ] =1;
                    coada_verificati.push( v[j1][j2].dest );
                }


            }


    for(i=2;i<=n;i++)
    {
        fout<<cost[i]<<" ";
    }


    return 0;
}