#include<bits/stdc++.h>
using namespace std;
ifstream fi("bellmanford.in");
ofstream g("bellmanford.out");

 struct muchie{
 long a,b,c;}e[250010];

 long long n,m,k,cost[50010],f[50010];
 vector<long>v[50010];
 vector< pair<long,long> >h;

 void tiere()
 {
     for(long i=1;i<=n;++i)
        cost[i]=1000000000;
        cost[1]=0;
        h.push_back(make_pair(0,1));
        make_heap(h.begin(),h.end());
 }

 void sol()
 {
     pair<long,long>per;
     long i,j,node,poz;
     long long pas=0;
     while(h.size() && pas<=1LL*n*m)
     {
         pas++;
         pop_heap(h.begin(),h.end());
         per=h.back();
         h.pop_back();
         node=per.second;
         f[node]=0;
         for(long j=0;j<v[node].size();++j)
         {
             poz=v[node][j];
             if(cost[e[poz].a]+e[poz].c<cost[e[poz].b])
             {
                 cost[e[poz].b]=cost[e[poz].a]+e[poz].c;
                 if(!f[e[poz].b])
                 {
                     f[e[poz].b]=1;
                     h.push_back(make_pair(-cost[e[poz].b],e[poz].b));
                     push_heap(h.begin(),h.end());
                 }
             }
         }
     }
 }

 long ver()
 {
     long i;
     for(i=1;i<=m;++i)
        if(cost[e[i].a]+e[i].c<cost[e[i].b])
        return 1;
     return 0;
 }

 int main()
 {
     fi>>n>>m;
     for(int i=1;i<=m;++i)
     {
         fi>>e[i].a>>e[i].b>>e[i].c;
         v[e[i].a].push_back(i);
     }
     tiere();
     sol();
     if(ver())
     {
         g<<"Ciclu negativ!";
         return 0;
     }
     for(long i=2;i<=n;++i)
        g<<cost[i]<<' ';
 }