#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <string.h>

#define NMAX 50001
#define MMAX 250001
#define INF 99999

using namespace std;

vector<pair<int, int> > adjList[NMAX];
int dist[NMAX];
bool visited[NMAX];
int n, m;
bool negativeCycle;
queue<int> q;
int nodes[NMAX];

void bellmanFord(int source) {

	memset(dist, n + 1, INF);
	visited[source] = true;
    dist[source] = 0;
    q.push(source);
 
    while(!q.empty() && !negativeCycle) {
        int node = q.front();
        q.pop();
        visited[node] = false;
 
        for (int i = 0; i < adjList[node].size(); ++i) {
        	pair<int, int> aux = adjList[node][i];
            if (dist[node] < INF) {
            	int alt = dist[node] + aux.second;
                if (dist[aux.first] > alt) {
                    dist[aux.first] = alt;
                    if (!visited[aux.first]) {
                        if (nodes[aux.first] > n) {
                            negativeCycle = true;
                        } else {
                            q.push(aux.first);
                            visited[aux.first] = true;
                            nodes[aux.first] ++;
                        }
                    }
                }
            }
        }
    }
}

int main() {
	FILE *in, *out;
	in = fopen("bellmanford.in", "r");
	out = fopen("bellmanford.out", "w");
	int a, b, l;
	fscanf(in, "%d%d", &n, &m);
	for (int i = 1; i <= m; ++i) {
		fscanf(in, "%d%d%d", &a, &b, &l);
		adjList[a].push_back(make_pair(b, l));
	}
	bellmanFord(1);
	if (negativeCycle) {
		fprintf(out, "Ciclu negativ!\n");
	} else {
		for (int i = 2; i <= n; ++i) {
			fprintf(out, "%d ", dist[i]);
		}
	}
	return 0;
}