#include <iostream>
#include<fstream>
#include<string.h>
#include<bits/stdc++.h>
#include<math.h>
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

#define NMAX 50005

vector<pair<int,int> > ma[NMAX];

int n,m;

void citire()
{
   fin>>n>>m;
   for(int i=1;i<=m;i++)
   {
      int x,y,c;
      fin>>x>>y>>c;
      ma[x].push_back(make_pair(y,c));
   }

}

int oo = (1<<30)-1;
int dist[NMAX];
int viz[NMAX];
queue<int> coada;
bool esteCoada[NMAX];

int Bellman_Ford(int s)
{
   for(int i=1;i<=n;i++)
      dist[i] = oo;

   dist[s] = 0;
   esteCoada[s] = true;
   coada.push(s);

   while(!coada.empty())
   {
      int nod = coada.front();
      coada.pop();
      esteCoada[nod] = false;
      viz[nod]++;
      if(viz[nod] >= n)
         return false;

      for(int i=0;i<ma[nod].size();i++)
      {
         int vecin = ma[nod][i].first;
         int cost = ma[nod][i].second;
         if(dist[vecin] > dist[nod] + cost)
         {
            dist[vecin] = dist[nod] + cost;
            if(!esteCoada[vecin])
            {
               esteCoada[vecin] = true;
               coada.push(vecin);
            }
         }
      }
   }


   for(int j=1;j<=n;j++)
   {
      for(int k = 0;k<ma[j].size();k++)
      {
         int vecin = ma[j][k].first;
         int cost = ma[j][k].second;
         if(dist[vecin] > dist[j] + cost)
         {
            return 0;
         }

      }
   }
   return 1;

}

int main(){

   citire();
   if(Bellman_Ford(1))
   {
      for(int i=2;i<=n;i++)
         fout<<dist[i]<<" ";
   }
   else
   {
      fout<<"Ciclu negativ!";
   }

   return 0;
}