#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;



         if(nrq[y]==n)



                     {



                        out<<"Ciclu negativ!";



                        exit(0);







                     }



         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]++;











                 }







              }







         }







    }























}



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;



}