#include <fstream>
#include <vector>
#include <queue>
#define DMAX 50005
#define INF 1000000000

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,tata[DMAX],d[DMAX],nrmax[DMAX];
void citire();
int bellman(int x0);
vector <int> LA[DMAX];
vector <int> c[DMAX];
queue <int> Q;
int main()
{int i;
    citire();
    if(bellman(1)==0)
       for(i=2;i<=n;i++)
           fout<<d[i]<<' ';
    fout<<'\n';
    return 0;
}
void citire()
{int i,x,y,cost;
 fin>>n>>m;
   for(i=1;i<=m;i++)
       {
        fin>>x>>y>>cost;
        LA[x].push_back(y);
        c[x].push_back(cost);
       }
}
int bellman(int x0)
{int ok,i,j;
 vector<int>::iterator k;
 vector<int>::iterator k1;
   for(i=1;i<=n;i++)
      {tata[i]=0;d[i]=INF;}
   d[x0]=0;
   for(i=1;i<=n;i++)
       Q.push(i);
   ok=0;
   while(Q.size())
        {j=Q.front();
          Q.pop();
          for(k=LA[j].begin(),k1=c[j].begin();k!=LA[j].end();++k,++k1)
            if(d[j]!=INF&&*k1!=INF)
               if(d[*k]>d[j]+(*k1))
                {
                  d[*k]=d[j]+(*k1);
                  tata[*k]=j;
                  Q.push(*k);
                  nrmax[*k]++;
                  if(nrmax[*k]>n)
                     {ok=1;break;}
                }
          if(ok==1)
             break;
        }
   if (ok==1) fout<<"Circuit negativ!";
   return ok;
}