#include <bits/stdc++.h>



using namespace std;





ifstream in("bellmanford.in");

ofstream out("bellmanford.out");



const int MAX=50001;
const int INF=1<<30;

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;
    for(int i=1;i<=n;i++) d[i]=INF;


    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;

}