#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define inf (1<<30);
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
vector <pair < int , int > >v[100005];
vector <int > g;
queue <int > coada;
int n, m , d[100005], viz[100005], incoada[100005];
int bellman (int k)
{for (int i=1;i<=n;i++)
      {d[i]=inf;
       viz[i]=incoada[i]=0;
      }
d[k]=0;
incoada[k]=1;
coada.push (k);
while (!coada.empty())
     {int cur=coada.front();
      coada.pop();
      if(viz[cur]>=n)
         return 0;
      incoada[cur]=0;
      for (int i=0;i<v[cur].size();i++)
          {int a=v[cur][i].first;
           int b=v[cur][i].second;
           if(d[cur]+b<d[a])
             {d[a]=b+d[cur];
              if(!incoada[a])
                 coada.push(a);
             }
          }
     }
    return 1;
}
int main()
{fin >> n >> m;
int x, y, z;
for (int i=1;i<=m;i++)
    {fin >> x >> y>>z;
     v[x].push_back(make_pair(y,z));
    }
    if(bellman(1))
     {for (int i=2;i<=n;i++)
           fout << d[i] << " ";
     }
     else fout << "Ciclu negativ";
    return 0;
}