#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int MAX_N = 50000;

struct Edge {
  int u;
  int cost;
};

vector<Edge> g[5 + MAX_N];
bool inQueue[5 + MAX_N];
int vis[5 + MAX_N];
int costMin[5 + MAX_N];

int main() {
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);

  int n, m;
  scanf("%d%d", &n, &m);

  for (int i = 1; i <= m; i++) {
    int u, v, cost;
    scanf("%d%d%d", &u, &v, &cost);
    g[u].push_back({v, cost});
    costMin[i] = 250000001;
  }

  queue<int> q;
  q.push(1);
  inQueue[1] = true;
  vis[1]++;
  costMin[1] = 0;

  while (!q.empty()) {
    int node;
    node = q.front();
    q.pop();
    inQueue[node] = false;

    if (vis[node] == n) {
      printf("Ciclu negativ!\n");
      return 0;
    }

    for (auto e : g[node]) {
      int u, cost;
      u = e.u;
      cost = e.cost;
      if (costMin[u] > costMin[node] + cost) {
        costMin[u] = costMin[node] + cost;
        if (!inQueue[u]) {
          q.push(u);
          inQueue[u] = true;
          vis[u]++;
        }
      }
    }
  }

  for (int i = 2; i <= n; i++)
    printf("%d ", costMin[i]);

  return 0;
}