#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int main() {
	freopen("bellmanford.in", "r", stdin);
	freopen("bellmanford.out", "w", stdout);

	int n, m, a, b, c;
	scanf("%d%d", &n, &m);
	vector<vector<int>> arcs(n+1);
	vector<vector<int>> weights(n+1);
	int dist[n+1];

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

	for(int i=0; i<m; ++i) {
		scanf("%d%d%d", &a, &b, &c);
		arcs[a].push_back(b);
		weights[a].push_back(c);
	}

    queue <int> q;
    q.push(1);
	for(int i=0; i<n; ++i) {
        m = q.size();
        for(int j=0; j<m; ++j) {
            a = q.front();
            q.pop();

            for(int k=0; k<arcs[a].size(); ++k)
                if (dist[a] + weights[a][k] < dist[arcs[a][k]]) {
                    dist[arcs[a][k]] = dist[a] + weights[a][k];
                    q.push(arcs[a][k]);
                }
        }
	}

    m = q.size();
	for (int j=0; j<m; ++j) {
        a = q.front();
        q.pop();
        for(int k=0; k<arcs[a].size(); ++k)
            if (dist[a] + weights[a][k] < dist[arcs[a][k]]) {
			printf("Ciclu negativ!\n");
			return 0;
		}
	}

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