#include <fstream>
#include <vector>
#include <queue>
#include <cstdlib>
#define INF 999999999
#define LMAX 50005

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

vector <int> G[LMAX];
vector <int> C[LMAX];

queue <int> Q;

int fol[LMAX];
int cmin[LMAX];
int n;

void citire();
void bellman_ford();
void afisare();

int main()
{
citire();
bellman_ford();
afisare();
fin.close();
fout.close();
return 0;
}

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

void bellman_ford()
    {
     int i;
     int x;
     for (i=2;i<=n;i++)
          cmin[i]=INF;
     Q.push(1);
     while (!Q.empty())
         {
          x=Q.front();
          Q.pop();
          for (i=0;i<G[x].size();i++)
              if (cmin[G[x][i]] > cmin[x]+C[x][i])
                 {
                  fol[G[x][i]]++;
                  cmin[G[x][i]]= cmin[x]+C[x][i];
                  if (fol[G[x][i]]==n)
                     {
                      fout<<"Ciclu negativ!\n";
                      exit(0);
                     }
                  Q.push(G[x][i]);
                 }
         }
    }

void afisare()
    {
     int i;
     for (i=2;i<=n;i++)
          fout<<cmin[i]<<' ';
    }