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

using namespace std;

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

struct data{

int origine;
int dest;
int cost;

};

//vector <data> v[50005];

int cost[50005];
data v[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++)
   {
       fin>>a>>b>>c;

       v[i].origine=a;
       v[i].dest=b;
       v[i].cost=c;

   }

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

   for(i=1;i<n;i++)
   {
       for(j1=1;j1<=m;j1++)
        if( cost[v[j1].origine]!=1005 )
            if(cost[ v[j1].origine ] + v[j1].cost < cost[ v[j1].dest ]  )
            {
                cost[ v[j1].dest ]=cost[ v[j1].origine ] + v[j1].cost;
            }



   }



   // vreificare ciclu negativ;

   for(j1=1;j1<=m;j1++)
        if( cost[v[j1].origine]!=1005 )
            if(cost[ v[j1].origine ] + v[j1].cost < cost[ v[j1].dest ]  )
            {
                fout<< "Ciclu negativ!";
                return 0;
            }


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


    return 0;
}