#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 ++)
      {
         int src  = E[j].x;
         int dest = E[j].y;
         int wgt  = E[j].wgt;
         if((D[src]!=INF) && (D[dest]>D[src]+wgt))
         {
            D[dest] = D[src]+wgt;
         }
      }
   }
   for(int j = 0; j < M; j ++)
   {
      int src  = E[j].x;
      int dest = E[j].y;
      int wgt  = E[j].wgt;
      if((D[src]!=INF) && (D[dest]>D[src]+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;
}