#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

#define INF 26000000

using namespace std;

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

int n, m;
vector < vector < pair < int, int > > > G;
queue <int> Q;

int cmin[50008];
int nr[50008];

int main() {

    int x, y, c;

    fin >> n >> m;

    G.resize(n + 2);
    for(int i = 1; i <= m; i++){
      fin >> x >> y >> c;
      G[x].push_back(make_pair(y, c));
    }

    int start = 1;

    for(int i = 1; i <= n; i++){
      if(i != start)
        cmin[i] = INF;
      else
        cmin[i] = 0;
    }

    Q.push(start);
    while(!Q.empty()){

        x = Q.front();
        for(int i = 0; i < G[x].size(); i++){

          y = G[x][i].first;
          c = G[x][i].second;
          if(cmin[y] > cmin[x] + c){
            cmin[y] = cmin[x] + c;
            nr[y]++;
            if(nr[y] == n){
              fout << "Ciclu negativ!";
              return 0;
            }
            Q.push(y);
          }

        }
        Q.pop();

    }

    for(int i = 2; i <= n; i++){
      fout << cmin[i] << ' ';
    }


    return 0;


}