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

using namespace std;

int mn[50001];

struct muchie {
  int dest, cost;
};

vector<muchie>v[50001];

queue<int>q;

int rep[50001];

int main() {
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int n, m, i, a, b, c, crt;
    cin>>n;
    cin>>m;
    for( i = 2; i <= n; i++ )
      mn[i] = 2100000000;
    for( i = 1; i <= m; i++ ) {
      cin>>a>>b>>c;
      v[a].push_back( { b, c } );
    }
    q.push( 1 );
    while( !q.empty() ) {
      crt = q.front();
      q.pop();
      if( rep[crt] == n ) {
        cout<<"Ciclu negativ!";
        return 0;
      } else rep[crt]++;
      for( i = 0; i < v[crt].size(); i++ ) {
        if( v[crt][i].cost + mn[crt] < mn[v[crt][i].dest] ) {
          mn[v[crt][i].dest] = v[crt][i].cost + mn[crt];
          q.push( v[crt][i].dest );
        }
      }
    }
    for( i = 2; i <= n; i++ )
      cout<<mn[i]<<" ";
    return 0;
}