#include  <iostream>
#include  <fstream>
#include  <vector>
#include  <queue>
#define pb push_back

using namespace std;

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

const int inf = 0x3f3f3f3f;
const int Nmax = 5e4 + 5;
vector < pair <int, int > > G[Nmax];
queue <int>Q;
int n, m;
int d[Nmax];
int vis[Nmax];
bool ok;

void read()
{
  in>>n>>m;
  for(int i = 1; i <= m; i++)
  {
    int x, y, c;
    in>>x>>y>>c;
    G[x].pb({y, c});
  }
}

void belman_ford(int  nod_s)
{
  Q.push(nod_s);
  for(int i = 2; i <= n; i++)
    d[i] = inf;
  while(!Q.empty())
  {
    int nod_c = Q.front();
    Q.pop();
    for(auto it : G[nod_c])
    {
      int cost = it.second;
      if(vis[it.first] > n-1){
        out<<"Ciclu negativ!";
        ok = 1;
        return;
      }
      else
      {
        if(d[nod_c] + cost < d[it.first]){
          d[it.first] = d[nod_c] + cost;
          Q.push(it.first);
          vis[it.first]++;
        }
      }
    }
  }
}


void solve()
{
  belman_ford(1);
}

void print()
{
  if(!ok)
  for(int i = 2; i <= n; i++)
  out<<d[i]<<' ';
}

int main()
{
  read();
  solve();
  print();
}