#include <bits/stdc++.h>

using namespace std;

const int NMAX = 50003;
const int INF = 1e9;

int n, m;
int dist[NMAX];
vector<vector<pair<int,int>>> g(NMAX);

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

    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++) {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        g[x].push_back({y, c});
    }
    fill(dist+1, dist+n+1, INF), dist[1] = 0;

    for(int i = 1; i <= n-1; i++) {
        for(int u = 1; u <= n; u++) {
            for(int j = 0; j < (int)g[u].size(); j++) {
                pair<int,int> v = g[u][j];
                dist[v.first] = min(dist[v.first], dist[u] + v.second);
            }
        }
    }

    bool hasNegativeCycles = 0;
    for(int u = 1; u <= n; u++) {
        for(int j = 0; j < g[u].size(); j++) {
            pair<int,int> v = g[u][j];
            if(dist[v.first] > dist[u] + v.second) hasNegativeCycles = 1;
        }
    }

    if(hasNegativeCycles) puts("Ciclu negativ!");
    else {
        for(int i = 2; i <= n; i++) {
            printf("%d ", dist[i]);
        }
    }
    return 0;
}