#include <bits/stdc++.h>

using namespace std;

const int nmax = 5e4 + 10;
const int inf = 0x3f3f3f3f;

int n, m;
int dist[nmax], cnt[nmax], in_st[nmax];
vector < pair < int, int > > g[nmax];

void input() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);

        g[x].push_back({y, z});
    }
}

void run_bellmanford() {
    memset(dist, inf, sizeof(dist));
    queue < int > st;

    st.push(1); dist[1] = 0; in_st[1] = 1;
    while (st.size()) {
        int node = st.front(); st.pop(); in_st[node] = 0;

        for (auto &it: g[node]) {
            if (dist[node] + it.second >= dist[it.first]) continue;

            if (cnt[it.first] == n - 1) {
                printf("Ciclu negativ!\n");
                exit(0);
            }

            cnt[it.first]++;
            dist[it.first] = dist[node] + it.second;
            if (!in_st[it.first])
                in_st[it.first] = 1, st.push(it.first);
        }
    }
}

void output() {
    for (int i = 2; i <= n; ++i)
        printf("%d ", dist[i]);
}

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

    input();
    run_bellmanford();
    output();

    return 0;
}