#include <bits/stdc++.h>
using namespace std;

const int DIM = 50005;
const int INF = 0x3f3f3f3f;

int dp[DIM], mod[DIM]; bool ins[DIM];
deque<int> que; vector<pair<int, int> > edg[DIM];

int main(void) {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y, c; scanf("%d %d %d", &x, &y, &c);
        edg[x].push_back(make_pair(y, c));
    }
    for (int i = 2; i <= n; ++i)
        dp[i] = INF;
    que.push_back(1); mod[1] = 1; ins[1] = true;
    for (; que.size(); que.pop_front()) {
        int x = que.front(); ins[x] = false;
        for (auto pr : edg[x]) {
            int y = pr.first, c = pr.second;
            if (dp[y] > dp[x] + c) {
                dp[y] = dp[x] + c;
                if (++mod[y] > n + 1) {
                    printf("Ciclu negativ!\n");
                    return 0;
                }
                if (!ins[y]) {
                    ins[y] = true;
                    que.push_back(y);
                }
            }
        }
    }
    for (int i = 2; i <= n; ++i)
        printf("%d ", dp[i]);
    return 0;
}