/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>
#include <random>
#include <deque>
#include <set>
#include <map>
#include <cmath>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

const int INF = 2e9;
const int N = 5e4;
const int M = 25e4;

struct Edge {
  int from, to, cost;
};
Edge v[1 + M];

int dist[1 + N];
int n, m;

void BellmanFord() {
  bool change;
  for(int i = 1; i <= n; i++) dist[i] = INF;
  dist[1] = 0;

  change = true;
  for(int i = 1; i < n && change; i++) {
    change = false;
    for(int j = 1; j <= m; j++) {
      Edge e = v[j];
      if(dist[e.from] + e.cost < dist[e.to]) {
        dist[e.to] = dist[e.from] + e.cost;
        change = true;
      }
    }
  }

  for(int j = 1; j <= m; j++) {
    Edge e = v[j];
    if(dist[e.from] + e.cost < dist[e.to]) {
      printf("Ciclu negativ!");
      exit(0);
    }
  }
}

int main() {
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= m; i++)
    scanf("%d%d%d", &v[i].from, &v[i].to, &v[i].cost);

  BellmanFord();
  for(int i = 2; i <= n; i++)
    printf("%d ", dist[i]);
  return 0;
}