#include <bits/stdc++.h>
#define inf 1e9
#define NMAX 50005
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector<pair<int,int> >v[NMAX];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >h;
int use[NMAX];
int d[NMAX],n,m,i,j,x,y,c,nod,vecin;
int main()
{
   f>>n>>m;
   for(i=1;i<=m;i++)
   {
       f>>x>>y>>c;
       v[x].push_back({y,c});
   }
   for(i=1;i<=n;i++)
   {
       d[i]=inf;
   }
   d[1]=0;
   h.push({0,1});
   while(!h.empty())
   {
       nod=h.top().second;
       h.pop();
       for(i=0;i<v[nod].size();i++)
       {
           vecin=v[nod][i].first;
           if(d[nod]+v[nod][i].second<d[vecin])
           {
               d[vecin]=d[nod]+v[nod][i].second;
               h.push({d[vecin],vecin});
           }
       }
       use[nod]++;
       if(use[nod]==n){g<<"Ciclu negativ!";return 0;}

   }
   for(i=2;i<=n;i++)
   {
       if(d[i]==inf)g<<"0"<<" ";
       else g<<d[i]<<" ";
   }
    return 0;
}