/*
 * Simple BellmanFord in O(N*M)
 * Algoritmul ia fiecare muchie de N ori.
 * Drumul minim va trece prin maxim N noduri.(altfel avem ciclu negativ)
 * De fiecare data cand luam muchiile odata ne apropiem cu on nod de acest drum minim.
 */

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

using namespace std;

const int NMAX = 50000;
const int MMAX = 250000;
const int INF = 0x7ffffff;

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

int n; int m;

class Edge {

public:
	int x; int y; int cost;

	Edge(){
		this->x = 0;
		this->y = 0;
		this->cost = 0;
	}

	Edge(int x, int y, int cost) {
		this->x = x;
		this->y = y;
		this->cost = cost;
	}
};

vector<Edge> edges;

int dist[NMAX + 1];


void read() {

	fin >> n >> m;

	for(int i = 1; i <= m ; ++i) {

		int x; int y; int cost;
		fin >> x >> y >> cost;
		edges.push_back(Edge(x, y, cost));
	}
}

bool bellmanFord(int start) {

    for(int i = 1; i <= n; ++i)
        dist[i] = INF;

    cout << INF << '\n';
    dist[start] = 0;

    for(int i = 1; i <= n + 1; ++i) {
        for(auto edge : edges) {

            if(dist[edge.x] + edge.cost < dist[edge.y])
                if(i == n + 1)
                    return false;
                else
                    dist[edge.y] = dist[edge.x] + edge.cost;
        }
    }

    return true;
}

int main() {

	read();

	if(bellmanFord(1))
        for(int i = 2; i <= n; ++i)
            fout << dist[i] << " ";
    else
        fout << "Ciclu negativ!";

	return 0;
}