#include <bits/stdc++.h>

using namespace std;


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

const int MAX=50001;
int n,m,st,dr,cost,x,y,c;
int d[MAX],nrq[MAX];
bool inq[MAX];

vector<pair<int,int> >graf[MAX];

void bellmanford(int start)
{
    queue<int>q;

    d[start]=0;
    inq[start]=true;

    nrq[start]++;

    q.push(start);

    while(!q.empty())
    {

         x=q.front();
         q.pop();
         inq[x]=false;

         for(int i=0;i<graf[x].size();i++)
         {
              pair<int,int> p=graf[x][i];
              y=p.first;
              c=p.second;

              if(d[x]+c<d[y])
              {
                 d[y]=d[x]+c;
                 if(!inq[y])
                 {
                     q.push(y);
                     inq[y]=true;
                     nrq[y]++;
                     if(nrq[y]==n)
                     {
                        out<<"Ciclu negativ";
                        exit(0);

                     }

                 }

              }

         }

    }





}
int main()
{
   in>>n>>m;

   for(int i=1;i<=m;i++)
   {
      in>>st>>dr>>cost;
      graf[st].push_back(make_pair(dr,cost));
       //graf[dr].push_back(make_pair(st,cost));

   }

   bellmanford(1);
   for(int i=2;i<=n;i++) out<<d[i]<<" ";

    return 0;
}