#include <fstream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
int n,m;
bool f=0;
 struct per
 {
     vector <int> p,c;
     int frecv=0;
 }v[50005];
 int pret[50005],viz[50005];
 bool prob[50005];


 void bellu()
 {
     queue <int> q;
     q.push(1);

     while(!q.empty())
     {
         int o=q.front();
         q.pop();
         prob[o]=0;
         viz[o]++;
         if(viz[o]>n)
         {
             f=1;
             cout<<"Ciclu negativ!";
             return;
         }

         for(int i=0;i<v[o].p.size();i++)
         {
             if(pret[v[o].p[i]]  >pret[o]+v[o].c[i]   )
             {
                 pret[v[o].p[i]] =pret[o]+v[o].c[i];
                 if(prob[v[o].p[i]]==0)
                 {
                     q.push(v[o].p[i]);
                     prob[v[o].p[i]]=1;

                 }

             }

         }
     }
     return ;

 }


int main()
{
     ios_base::sync_with_stdio(false);
     cin.tie(NULL);


     cin>>n>>m;
     for(int i=2;i<=n;i++)
     {
         pret[i]=(1<<30);
     }
     for(int i=1;i<=m;i++)
     {
         int a,b,co;
         cin>>a>>b>>co;

         v[a].p.push_back(b);
         v[a].c.push_back(co);



     }

     bellu();
     if(f==0)
     {
         for(int i=2;i<=n;i++)
         {
             cout<<pret[i]<<" ";
         }
     }





    return 0;
}