#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int NMAX = 50005;
const int INF = 1000000000;
struct Muchie {
    int x;
    int cost;
};
vector <Muchie> vec[NMAX];
queue <int> q;
bool in_queue[NMAX];
int parc[NMAX];
int cost[NMAX];

int main() {
    int n, m;
    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, cost;
        scanf("%d%d%d", &x, &y, &cost);
        vec[x].push_back({y, cost});
    }
    for(int i = 1; i <= n; i++) {
        cost[i] = INF;
    }
    cost[1] = 0;
    q.push(1);
    parc[1] = 1;
    in_queue[1] = 1;
    bool ok = 0;
    while(ok == 0 && !q.empty()) {
        int nr = q.front();
        q.pop();
        in_queue[nr] = 0;
        for(auto v : vec[nr]) {
            if(cost[v.x] > cost[nr] + v.cost) {
                cost[v.x] = cost[nr] + v.cost;
                if(in_queue[v.x] == 0) {
                    if(parc[v.x] > n) {
                        ok = 1;
                    }
                    else {
                        q.push(v.x);
                        in_queue[v.x] = 1;
                        parc[v.x]++;
                    }
                }
            }
        }
    }
    if(ok == 1) {
        printf("Ciclu negativ!\n");
        return 0;
    }
    for(int i = 2; i <= n; i++) {
        printf("%d ", cost[i]);
    }
    printf("\n");
    return 0;
}