#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50000;
const int INF = 1e8;

struct Edge{
  int dest, cost;
};

vector<Edge> G[NMAX + 1];
int dist[NMAX + 1], n, m;

bool bellman_ford( int source ) {
  bool imbunatatire = false;
  for( int i = 1; i <= n; i ++ )
    for( const auto &it : G[i] )
      if( dist[it.dest] > dist[i] + it.cost )
        dist[it.dest] = dist[i] + it.cost, imbunatatire = true;
  return imbunatatire;
}

int main() {
    fin>>n>>m;
    for( int i = 1; i <= m; i ++ ) {
      int u, v, cost;
      fin>>u>>v>>cost;
      G[u].push_back({v, cost});
    }
    for( int i = 1; i <= n; i ++ )
      dist[i] = INF;
    int source = 1;
    dist[source] = 0;
    for( int i = 1; i < n; i ++ )
      bellman_ford(source);

    if( bellman_ford(source) == true )
      fout<<"Ciclu negativ!";
    else {
      for( int i = 2; i <= n; i ++ )
        fout<<dist[i]<<" ";
    }
    return 0;
}