#include <bits/stdc++.h>
#define NMAX 50000
#define INF 100000000

using namespace std;

struct Edge{
  int dest;
  int cost;
};

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

int bellman_ford( int source ) {
  dist[source] = 0;
  q.push(source);
  while( !q.empty() ) {
    int node = q.front();
    q.pop();
    for( auto it : G[node] ) {
      if( dist[node] + it.cost < dist[it.dest] ) {
        viz[it.dest] ++;
        if( viz[it.dest] == n )
          return 0;
        dist[it.dest] = dist[node] + it.cost;
        q.push(it.dest);
      }
    }
  }
  return 1;
}

int main() {
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    int i, a, b, c;
    fin>>n>>m;
    for( i = 1; i <= m; i ++ ) {
      fin>>a>>b>>c;
      G[a].push_back({b,c});
      viz[a] = 0;
    }
    for( i = 1; i <= n; i ++ )
      dist[i] = INF;
    if( bellman_ford(1) )
      for( i = 2; i <= n; i ++ )
        fout<<dist[i]<<" ";
    else
      fout<<"Ciclu negativ!";
    return 0;
}