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

#define MAXN 50000
#define INF 2000000000

using namespace std;

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

int n, m;

int dist[MAXN+5];
bool inq[MAXN+5], viz[MAXN+5];

struct Edge
{
  int node, d;
};

vector<Edge> g[MAXN+5];

bool init( )
{
  for( int i=1;i<=n;i++ )
  {
    dist[i]=INF;
    viz[i]=0;
    inq[i]=false;
  }
}

bool bellman( int source )
{
  queue<int> q;

  init();
  dist[source]=0;

  q.push(source);

  while( !q.empty() )
  {
    int f=q.front();

    q.pop();
    inq[f]=false;

    if( ++viz[f]==n )
      return 0;

    for( vector<Edge>::iterator it=g[f].begin();it!=g[f].end();it++ )
      if( dist[f]+it->d<dist[it->node] )
      {
        dist[it->node]=dist[f]+it->d;

        if( !inq[it->node] )
        {
          q.push(it->node);
          inq[it->node]=true;
        }
      }
  }

  return 1;
}

int main()
{
  cin>>n>>m;

  while( m-- )
  {
    int a, b, c;

    cin>>a>>b>>c;

    g[a].push_back({b,c});
  }

  if( bellman(1) )
    for( int i=2;i<=n;i++ )
      cout<<dist[i]<<" ";
  else
    cout<<"Ciclu negativ!";

  return 0;
}