#include <fstream>
#include <vector>
#include <queue>

#define NMAX 50002
#define MMAX 250002
#define INF 1e9

using namespace std;

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

struct arc{int x, c;};
vector<arc> G[NMAX]; //liste de adiacenta dinamic cu costuri
int n, m;

queue<int> Q;
int nr[NMAX];
int cost[NMAX];

void citire();
void bellmanford();

int main()
{
    citire();
    bellmanford();
    return 0;
}

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

void bellmanford()
{
 int i, nod;
 bool cicluneg = 0; //flag care imi indica daca am gasit sau nu ciclu negativ
 arc aux;
 for(i = 1; i <= n; i++) cost[i] = INF;
 cost[1] = 0; Q.push(1);
 while(!Q.empty() && !cicluneg)
 {
      nod = Q.front(); Q.pop();
      for(i = 0; i < G[nod].size(); i++)
      {
          aux = G[nod][i];
          if(cost[aux.x] > cost[nod] + aux.c)
          {
             cost[aux.x] = cost[nod] + aux.c;
             Q.push(aux.x);
             nr[aux.x]++;
             if(nr[aux.x] == n) cicluneg = 1;
          }
      }
 }
 if(cicluneg) fout<<"Ciclu negativ!"<<'\n';
   else
   {
      for(i = 2; i <= n; i++) fout<<cost[i]<<' ';
      fout<<'\n';
   }
}