#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#include <algorithm>
#include <cassert>
using namespace std;

#define MAX 50050
#define INF 0x7FFFFFFF

vector<pair<int,int>> g[MAX];
int n, m;
set<int> s1, s2;
int d[MAX];

void bellman() {
    int x, y, z;
    s1.insert(1);
    for (int i = 1; i <= n; ++i) d[i] = INF;
    d[1] = 0;
    for (int i = 1; i <= n; ++i) {
        while (s1.size() > 0) {
            int x = *s1.begin();
            s1.erase(s1.begin());
            for (int j = 0; j < g[x].size(); ++j) {
                y = g[x][j].first;
                z = g[x][j].second;
                if (d[y] > d[x] + z) {
                    d[y] = d[x] + z;
                    s2.insert(y);
                }
            }
        }
        swap(s1, s2);
    }
    if (s1.size() > 0) {
        cout << "Ciclu negativ!";
    } else {
        for (int i = 2; i <= n; ++i) {
            printf("%d ", d[i]);
        }
    }
}

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

    scanf("%d %d", &n, &m);

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

    bellman();

    return 0;
}