/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <fstream>
#define debug(x) cerr << #x << " " << x << '\n'
#define debugsp(x) cerr << #x << " " << x << ' '

using namespace std;

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

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]) {
      out << "Ciclu negativ!\n";
      exit(0);
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  in.tie(nullptr); out.tie(nullptr);
  in >> n >> m;
  for(int i = 1; i <= m; i++)
    in >> v[i].from >> v[i].to >> v[i].cost;

  BellmanFord();
  for(int i = 2; i <= n; i++)
    out << dist[i] << ' ';  
  return 0;
}