#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];
	int times_in_queue[n+1];

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

	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);
    while(q.size()) {
        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]);
                ++ times_in_queue[arcs[a][k]];

                if (times_in_queue[arcs[a][k]] > n) {
                    printf("Ciclu negativ!\n");
                    return 0;
                }
            }
	}

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