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

using namespace std;

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

#define INF (1 << 30)
#define NMAX 50005

struct bf {
  int first, second;
  bool operator < ( const bf& other ) const {
    return second > other.second;
  }
};

vector<bf> G[NMAX];
priority_queue<bf> q;
int dist[NMAX], n, m, checked[NMAX];

void BF () {
  int i;
  bf node;
  while ( !q.empty() ) {
      node.first = q.top().first;
      node.second = q.top().second;
      q.pop();
      checked[node.first]++;
      if ( checked[node.first] <= m && node.second == dist[node.first] ) {
        for ( bf copil : G[node.first] ) {
          if ( dist[copil.first] > node.second + copil.second ) {
            dist[copil.first] = node.second + copil.second;
            q.push(copil);
          }
        }
      }
      else if ( checked[node.first] > m ) {
        cout << "Ciclu Negativ!\n";
        return;
      }
  }
  for ( i = 2; i <= n; i++ ) {
    cout << dist[i] << " ";
  }
  cout << "\n";
}

int main()
{
    int i, a, b, cost;
    cin >> n >> m;
    for ( i = 1; i <= m; i++ ) {
      cin >> a >> b >> cost;
      G[a].push_back({b, cost});
    }
    dist[1] = 0;
    for ( i = 2; i <= n; i++ )
      dist[i] = INF;
    q.push({1, 0});
    BF();
    return 0;
}