#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,i,j,d[50001],v[50001],contor[50001],sw=0;
struct nod{
   int inf,drum;
   nod *urm;
}*L[50001];
class comp{
   public:
       bool operator() (const int &a,const int &b){
            return d[a]>d[b];
       }
};
priority_queue<int,vector<int>,comp>Q;
void adaugsf(nod *&vf,int val1,int val2){
    nod *q;
    q=new nod;
    q->inf=val1;
    q->drum=val2;
    q->urm=vf;
    vf=q;
}
void cit(){
    fin>>n>>m;
    int a,b,c;
    for (i=1;i<=n;i++)
        L[i]=0;
    for (i=1;i<=m;i++){
        fin>>a>>b>>c;
        adaugsf(L[a],b,c);
    }
    fin.close();
}
void bford(int r){
   d[r]=0;
   nod *q;
   int x;
   v[r]=0;
   Q.push(r);
   while(!Q.empty() && sw==0){
       x=Q.top();
       Q.pop();
       q=L[x];
       v[x]=0;
       while(q!=0){
           if (d[q->inf]>d[x]+q->drum){
             d[q->inf]=d[x]+q->drum;
             if (v[q->inf]==0)
               if (contor[q->inf]>n) sw=1;
                 else{
                    v[q->inf]=1;
                    Q.push(q->inf);
                    contor[q->inf]++;
                 }
           }
           q=q->urm;
       }
   }
}
int main(){
   cit();
   for (i=1;i<=n;i++)
    d[i]=250000000;
   bford(1);
   if (sw==1) fout<<"Ciclu negativ!";
     else
        for (i=2;i<=n;i++)
        fout<<d[i]<<" ";
   fout.close();
   return 0;
}