#include <bits/stdc++.h>

using namespace std;

const int MAX_V = 50005;
const int INF = 1 << 30;

int n, m;

vector < pair < int, int > > G[MAX_V];

int cost[MAX_V];
int visited[MAX_V];
queue < int > q;

int main() {
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v, c;
    scanf("%d %d %d", &u, &v, &c);
    G[u].push_back(make_pair(v, c));
  }
  for (int i = 1; i <= n; ++i) {
    cost[i] = INF;
  }
  cost[1] = 0;
  q.push(1);
  while (q.size() > 0) {
    int u = q.front();
    q.pop();
    ++visited[u];
    if (visited[u] > n) {
      printf("Ciclu negativ!\n");
      return 0;
    }
    for (pair < int, int > v : G[u]) {
      if (cost[v.first] > cost[u] + v.second) {
        cost[v.first] = cost[u] + v.second;
        q.push(v.first);
      }
    }
  }
  for (int i = 2; i <= n; ++i) {
    printf("%d ", cost[i]);
  }
  return 0;
}