#include<bits/stdc++.h>
using namespace std;

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

#define MAX_N 50000
int n, m;
vector< pair<int, int> > graph[MAX_N];
bool marked[MAX_N];
int d[MAX_N], used[MAX_N];

bool cycle = false;

void bellmanFord() {
  for (int i = 0; i < MAX_N; ++i) {
    used[i] = 0;
    d[i] = INT_MAX;
  }

  queue<int> myQueue;
  d[0] = 0;
  myQueue.push(0);
  ++used[0];
  marked[0] = true;

  while (!myQueue.empty()) {
    int node = myQueue.front();
    myQueue.pop();

    for (auto neighbour : graph[node]) {
      if (d[neighbour.first] <= d[node] + neighbour.second)
        continue;
      if (used[node] >= n) {
        cycle = true;
        return;
      }

      d[neighbour.first] = d[node] + neighbour.second;
      if (!marked[neighbour.first]) {
        myQueue.push(neighbour.first);
        ++used[neighbour.first];
        marked[neighbour.first] = true;
      }
    }

    marked[node] = false;
  }
}

int main() {
  fin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int x, y, c;
    fin >> x >> y >> c;
    --x, --y;

    graph[x].push_back( {y, c} );
  }

  bellmanFord();

  if (cycle) {
    fout << "Ciclu negativ!\n";
    return 0;
  }
  for (int i = 1; i < n; ++i) {
    fout << d[i] << " ";
  }
}