#include <iostream>
#include <fstream>
#include <deque>
#include <vector>

#define N 50005
#define pinf 5000030000
using namespace std;

long long D[N];
unsigned short fr[N];

vector <vector< pair< int, int> > >L(N);
deque <int> coada;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int m,n,cn;

void bellford(int r)
{
    int x,i;

    for(i=1;i<=n;i++)
        D[i]=pinf;

    coada.push_back(r);D[r]=0; fr[r]++;
    while(!coada.empty() && !cn)
    {
        x=coada.front();coada.pop_front();

        //parcurgem lista de adiacenta a lui x
        for(i=0;i<L[x].size();i++)
           if(D[L[x][i].first]>D[x]+L[x][i].second )
           {
                fr[L[x][i].first]++;
                if(fr[L[x][i].first]>n) cn=1;
                else
                {
                  D[L[x][i].first]=D[x]+L[x][i].second;
                  coada.push_back(L[x][i].first);
                }
           }
    }
}
int main()
{
   int i,x,y,c;
   f>>n>>m;
   for(i=1;i<=m;i++)
   {
      f>>x>>y>>c;
      L[x].push_back(make_pair(y,c));
   }

   bellford(1);

   if(cn) g<<"Ciclu negativ!";
   else
     for(i=2;i<=n;i++)
        if(D[i]!=pinf) g<<D[i]<<" ";

    return 0;
}