#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <climits>
using namespace std;

const int kNmax = 50005;
const int kMmax = 250005;

class Task {
 public:
	void solve() {
		read_input();
    get_result();
	}

struct Edge {
    int x, y;
    int c;
};

 private:
	int n, m;
  vector<Edge> edges;
  int dist[kNmax];

	void read_input() {
		ifstream fin("bellmanford.in");
		fin >> n >> m;

    for(int i = 1; i <= n; i++) {
      dist[i] = INT_MAX / 3;
    }

    dist[1] = 0;

    int x, y, c;
		for (int i = 1; i <= m; i++) {
    fin >> x >> y >> c;
    Edge newEdge;
    newEdge.x = x;
    newEdge.y = y;
    newEdge.c = c;
    edges.push_back(newEdge);
    }

		fin.close();
	}

	void get_result() {
    ofstream fout("bellmanford.out");
    for (int i = 1; i <=n; i++) {
      for (int j = 0;  j < m; j++) {
        int x = edges[j].x;
        int y = edges[j].y;
        int c = edges[j].c;
        if (dist[x] != INT_MAX / 3 && dist[x] + c < dist[y])
                dist[y] = dist[x] + c;
      }
    }

    for (int j = 0; j < m; j++){
      int x = edges[j].x;
      int y = edges[j].y;
      int c = edges[j].c;
       if (dist[x] != INT_MAX / 3 && dist[x] + c < dist[y])
          fout << "Ciclu negativ!";
   }

    for (int i = 2; i <=n; i++)
    fout<<dist[i]<<" ";

    fout<<endl;
   fout.close();
	}


};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}