#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int Nmax = 50005;
const int Mmax = 250005;
const int INF  = 2000000000;

struct edge
{
   int x, y;
   int wgt;
};

int N, M;
int D[Nmax];
bool negativeCycle = false;
edge E[Mmax];

void read()
{
   ifstream f("bellmanford.in");
   f >> N >> M;
   for(int i = 0; i < M; i ++)
   {
      f >> E[i].x >> E[i].y >> E[i].wgt;
   }
   f.close();
}

void BellmanFord(int Node)
{
   for(int i = 1; i <= N; i ++)
   {
      D[i] = INF;
   }
   D[Node] = 0;
   for(int i = 0; i < N-1; i ++)
   {
      for(int j = 0; j < M; j ++)
      {
         D[E[i].y] = min(D[E[i].y],D[E[i].x]+E[i].wgt);
      }
   }
   for(int i = 0; i < M; i ++)
   {
      if(D[E[i].y] > D[E[i].x]+E[i].wgt)
      {
         negativeCycle = true;
      }
   }
}

void print()
{
   ofstream g("bellmanford.out");
   if(negativeCycle)
   {
      g << "Ciclu negativ!";
   }
   else
   {
      for(int i = 2; i <= N; i ++)
      {
         g << D[i] << " ";
      }
   }
   g.close();
}

int main()
{
    read();
    BellmanFord(1);
    print();
    return 0;
}